In which we prove that the basic implementation of the push-relabel algorithm runs in time .
1. The Push-Relabel Algorithm
In the last lecture we described the push-relabel method to solve the maximum flow problem.
In this method, instead of maintaining a feasible flow, and improving it until it becomes optimal, we maintain a preflow, which is an assignment of flows to edges that allows vertices to have more incoming flow than outgoing flow (but not vice versa) and that satisfies the capacity constraints.
Definition 1 (Preflow) An assignment of a non-negative flow to each edge of a network is a preflow if
- for each edge ,
- for each vertex ,
we define the excess flow at as
Furthermore, we will also assume that if is a flow or a preflow, then it is never the case that there are two vertices such that both and . (We can always transform an arbitrary flow or preflow to an equivalent one that satisfies this condition, by subtracting the minimum of the two amounts from both and . The algorithm will automatically construct preflows that satisfy the condition.)
The residual network with respect to a preflow is defined like the residual network of a flow. The capacity of an edge in the residual network is
At the start of the algorithm, sends flow to its neighbors, completely saturating all its outgoing edges. This means that, at the start of the algorithm, is not reachable from in the residual network. The algorithm will maintain this invariant through every step.
Eventually, the algorithm reaches a point at which all the excess flows are zero at all vertices (except and ), which means that the preflow is actually a feasible flow. Since we maintained the invariant that there is no path from to in the residual network, the flow that we have at that point is an optimal flow. To eventually reach a feasible flow, we want to push flow out of vertices that have positive excess flow, but we want to do so in a carefully arranged way so that the algorithm converges quickly. The algorithm maintains, for every vertex , a height . Through the various phases of the algorithm, the heights will “self-organize” so that the flow will mostly flow downhill, and the heights will roughly correspond to the distance from a vertex to . (The actual behavior will be somewhat more complicated.)
At each step, we pick a vertex with positive excess flow, and select an outgoing edge with positive residual capacity, and push flow out of and into , provided that is “downhill from ,” that is, . If there is no vertex for which we can do such a push operation, we take any vertex with positive excess flow, and increase its height. (This is called a relabel operation.)
This is all that the algorithm is doing, and the following is a complete description of the algorithm:
- Input: network
- for each do
- for each do
- while is not a feasible flow
- let be the capacities of the residual network
- if there is a vertex and a vertex such that , , and then
- push units of flow on the edge
- else, let be a vertex such that , and set
Note that, by this description, it is not even clear that the algorithm converges in finite time. Our goal today is to show that it does, and to prove that the running time is .
2. Analysis of the Push-Relabel Algorithm
We begin by showing that no vertex can reach a height bigger than . This automatically puts an upper bound to the number of relabel operations that can be executed, and is an important starting point in analyzing the number of push operations.
Proof: First, let us why this is “obvious:” in a preflow, vertices are allowed to “destroy” stuff, but not to “create” it, so if a vertex has positive excess flow, then in particular it has positive incoming flow, and the incoming stuff must be coming from along a path made of edges with positive flow. To each such edge corresponds an edge in the opposite direction with positive capacity in the residual network, and so is connected to in the residual network.
The only part of the above argument that is not rigorous is when we say that if a vertex has positive excess flow then there must be a path from to made entirely of edges with positive flow. Let be the set of vertices which are reachable from via such a path. Because of the preflow constraints on the vertices , we have
but, in the second expression, all terms of the form in which and cancel, because they appear once with a plus sign and once with a minus sign. The result of such cancellations is
where the last inequality follows from the fact that must be zero when and . So we have that for every , which means that every vertex that has must be in , and so it must be reachable from via a path made of edges with positive flow.
The connection between the previous lemma and the task of bounding the heights of vertices comes from the following observation.
Lemma 3 At every step, if there is an edge that has positive capacity in the residual network, then
Before proving the lemma, let us understand what it is getting at. Our intuition for the heights, is that we want the flow to go “downhill,” and in fact every time we do a push operation we do so from a higher vertex to a lower one. If the flow goes downhill, the edges with positive residual capacity go “uphill.” This is not exactly true at each step, because of the relabeling operations, but the lemma is saying that edges with positive residual capacity cannot go downhill by more than one unit. Proof: We show that the property is an invariant preserved by the algorithm at each step. At the beginning, the residual network contains: (i) the edges of the original networks between vertices other than , and all such vertices have the same height 0, and (ii) edges from the neighbors of to , and such edges go uphill. Now we show that the property is preserved at each step. If we do a relabel step on a vertex , the property remains true for all the edges with positive capacity coming into . About the edges with positive capacity coming out of , if we did a relabel step it was because we had ; after the relabel, we still have .
If we do a push step along an edge , we might introduce the reverse edge in the residual network. The push step, however, happens only when , and so the edge satisfies the property.
Fact 4 At every step, if there is a path from to in the residual network, then
Proof: If there is a path of length from to in the residual network, then, by applying times Lemma 2, we have , and if there is a path from to there must be a path of length at most .
We can now being to draw conclusions that are relevant to our analysis.
Fact 5 At each step of the algorithm, there is no path from to in the residual network.
Because, if there were such a path, we would have , but at the beginning we have and , and the heights of and never change.
This means that if the algorithm terminates, then it outputs an optimal flow. From now on, it remains to estimate the running time of the algorithm, which we do by finding upper bounds to the number of times the various operations can be executed.
Fact 6 At each step of the algorithm, every vertex has height at most .
Proof: Each time the height of a vertex is increased, it is because it has positive excess flow. If a vertex has positive excess flow, then there is a path from to in the residual network. If there is such a path, then .
Fact 7 The algorithm executes at most relabel operations.
Proof: There are at most vertices on which the relabel operation is admissible, and on each of them the algorithm executes the operation at most times.
We now estimate the number of push operations.
We call a push operation saturating if it uses the entire residual capacity of edge, making it disappear from the residual network. Otherwise, the push operation is nonsaturating.
Fact 8 The algorithm executes at most saturating push operations.
Proof: Consider an edge . The first time there is a saturating push from to , it is because . After the saturating push, the edge disappears from the residual network, and so there cannot be any other saturating push from to (and, indeed, no push of any kind), until sends back some flow to with a push in the opposite direction. But for this to happen we must first have , which requires at least two relabels of . For the next saturating push from to , we must have again , which requires two more relabels, at least. So, between two saturating pushes from to , at least four relabels must take place on and . Overall, and can relabeled at most times, and so there can be at most saturating pushes.
There are edges that can appear in the residual network, and so in total we have at most saturating pushes.
The most interesting part of the analysis is how we analyze the number of non-saturating push operations.
At each step of the execution of the algorithm, we define the “energy” of the current preflow as
the sum of the heights of all vertices that have positive excess flow. The algorithm starts in a zero-energy state, but the energy becomes one after the first relabel operation. When the energy becomes zero again, it is because there are no nodes with excess flow, and the algorithm stops.
We have the following observations.
Fact 9 Each relabel step increases the energy by exactly one unit.
Fact 10 Each saturating push increases the energy by at most units.
Proof: A push step along an edge does not change the height of any vertex, but it could give excess flow to vertex , which possibly had zero excess flow before, so that the energy increases by units.
Fact 11 Each nonsaturating push decreases the energy by at least one unit.
Proof: If we do a push on an edge , why would the push be nonsaturating? The only reason why we would not saturate the edge is that the excess flow of is less than the residual capacity of , and so we can push the entire excess flow of along with residual capacity to spare. But this means that, after a nonsaturing push along , the excess flow of becomes zero, and so is not counted in the energy any more. It is possible that had no excess flow before the push and now it does, which means that we need to add in the energy, but we still have that the new energy is at most the old energy minus plus and, recalling that we do a push only if , we have that the new energy is at most the old energy minus one.
Fact 12 The total number of nonsaturating pushes is at most .
Proof: If, at some step of the execution of the algorithm, the preflow is not yet a feasible flow, then the energy must by . If, up to that point, the algorithm has executed relabel operations, saturating push operations, and nonsaturating push operations, then
we now that and , so the above expression implies
So if, at some point of the execution of the algorithm, we haven’t reached the termination condition yet, this implies that we have executed fewer than nonsaturating pushes.
Equivalently, when the algorithm terminates, it has executed at most nonsaturating pushes.
Overall, we have a total of at most operations, and each can be implemented in time, so the running time of the algorithm is .
3. Improved Running Time
We note that the algorithm is somewhat underspecified, in the sense that there could be more than one vertex out of which a push operation is allowed, and we are not saying how to pick one; if no push operation is possible, any of the vertices with positive excess can be picked for a relabel operation, and we are not specifying how to pick one. The analysis of the running time applies to any possible way to make such choices.
A reasonable heuristic is that if we have the choice of multiple vertices out of which to push flow, then we choose the vertex of biggest height. It can be proved (but we will not), this implementation of the algorithm executes at most nonsaturating pushes, and so the running time is . A more complicated implementation, in which multiple pushes are done together, and the dynamic tree data structure is used to keep information about the current preflow, has running time . In terms of worst-case running time, this is the best known for strongly polynomial algorithms.
An algorithm of Goldberg and Rao has running time
In the interesting case in which , this is roughly , compared the to the running time of the optimized push-relabel algorithm. This year, a new algorithm has been discovered that, in undirected networks, finds a flow of cost in time .
There has been extensive experimental analysis of maximum flow algorithms. The fastest algorithms in practice are carefully tuned push-relabel implementations.