In which we prove that the Edmonds-Karp algorithm for maximum flow is a strongly polynomial time algorithm, and we begin to talk about the push-relabel approach.
1. Flow Decomposition
In the last lecture, we proved that the Ford-Fulkerson algorithm runs in time
if the capacities are integers and if we pick, at each step, the fattest path from to in the residual network. In the analysis, we skipped the proof of the following result.
We derive the theorem from the following result.
- the cost of is equal to the sum of the costs of the flows
- the flow sends positive flow only on the edges of .
We apply Lemma 2 to the maximum flow of cost , and we find flows and paths as in the Lemma. From the first two properties, we get that there is an such that the cost of the flow is at least . From the third property, we have that the units of flow of are carried using only the path , and so every edge of must have capacity at least .
It remains to prove the Lemma.
Proof: (Of Lemma 2) Now we see how to construct flows with the above three properties. We do so via the following procedure:
- find a path from to using only edges such that , and call it
- let be the minimum of among the edges
- let for each and for the other edges
- let for each
The “residual” flow is initialized to be equal to , and so its cost is the same as the cost of . At every step , if the cost of is still positive, we find a path from to entirely made of edges with positive flow.
(Note that such a path must exist, because, if not, call the set of nodes reachable from using edges that have ; then contains and it does not contain , and so it is a cut and the net flow out of is equal to cost of ; but there is no positive net flow out of , because all the edges from vertices of to vertices not in must have ; this means that the cost of must also be zero, which is a contradiction.)
We define the flow by sending along the smallest of the amounts of flow sent by along the edges of . Note that is feasible, because for every edge we have and, by construction, we also have , and was a feasible flow and so . We then decrease by on each edge. This is still a feasible flow, because we leave a non-negative flow on each edge and we can verify that we also maintain the conservation constraints. After the update, the cost of decreases precisely by the same amount as the cost of , so we maintain the invariant that, after steps, we have
It remains to observe that, after the update of , at least one of the edges that had positive has now . (This happens to the edge, or edges, that carry the minimum amount of flow along .) This means that, after steps, the number of edges such that is at most and that, in particular, the algorithm halts within at most iterations.
Call the number of iterations after which the algorithm halts. When the algorithm halts, , and so we have
and so the flows and paths found by the algorithm satisfy all the requirements stated at the beginning.
The running time is not terrible, especially considering that it is a worst-case estimate and that often one has considerably faster convergence in practice. There is, however, an undesirable feature in our analysis: the running time depends on the actual values of the numbers that we get as input. An algorithm for a numerical problem is called strongly polynomial if, assuming unit-time operations on numerical quantities, the running time is at most a polynomial in the number of numerical quantities that we are given as input. In particular, a maximum flow algorithm is strongly polynomial if it runs in time polynomial in the number of edges in the network.
Today we describe the Edmonds-Karp algorithm, which is a simple variant of the Ford-Fulkerson algorithm (the variant is that, in each iteration, the path in the residual network is found using a BFS). The Edmonds-Karp algorithm runs in strongly polynomial time in a simple implementation, and the worst-case running time can be improved to with some adjustments.
We then begin to talk about an approach to solving the maximum flow problem which is rather different from the Fulkerson-Ford approach, and which is based on the “push-relabel” method. A simple implementation of the push-relabel method has running time , and a more sophisticated implementation has worst-case running time . We will only present the simpler algorithm.
2. The Edmonds-Karp Algorithm
The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson algorithm in which, at every step, we look for an path in the residual network using BFS. This means that, if there are several possible such paths, we pick one with a minimal number of edges.
From now on, when we refer to a “shortest path” in a network, we mean a path that uses the fewest edges, and the “length” of a path is the number of edges. The “distance” of a vertex from is the length of the shortest path from to the vertex.
BFS can be implemented in time, and so to complete our analysis of the algorithm we need to find an upper bound to the number of possible iterations.
The following theorem says that, through the various iterations, the length of the shortest path from to in the residual network can only increase, and it does increase at the rate of at least one extra edge in the shortest path for each iterations.
Theorem 3 If, at a certain iteration, the length of a shortest path from to in the residual network is , then at every subsequent iteration it is . Furthermore, after at most iterations, the distance becomes .
Clearly, as long as there is a path from to , the distance from to is at most , and so Theorem 3 tells us that, after at most iterations, and must become disconnected in the residual network, at which point the algorithm terminates. Each iteration takes time , and so the total running time is .
Let us now prove Theorem 3.
Proof: Suppose that, after some number of iterations, we have the residual network and that, in the residual network, the length of the shortest path from to is . Construct a BFS tree starting at , and call , , , , the vertices in the first, second, -th, , layer of the tree, that is, the vertices whose distance from is 1, 2, , and so on. Note that every edge in the network is such that if and then , that is, nodes can go from higher-numbered layer to lower numbered layer, or stay in the same layer, or advance by at most one layer.
Let us call an edge a forward edge if, for some , and . Then a shortest path from to must use a forward edge at each step and, equivalently, a path that uses a non-forward edge at some point cannot be a shortest path from to .
What happens at the next iteration ? We pick one of the length- paths from to and we push flow through it. In the next residual network, at least one of the edges in disappears, because it has been saturated, and for each edge of we see edges going in the opposite direction. Now it is still true that for every edge of the residual network at the next step , if and , then (where are the layers of the BFS tree of the network at iteration ), because all the edges that we have added actually go from higher-numbered layers to lower-numbered ones. This means that, at iteration the distance of from is still at least , because and, at every step on a path, we can advance at most by one layer.
(Note: we have proved that if the distance of from is at one iteration, then it is at least at the next iteration. By induction, this is enough to say that if will always be at least in all subsequent iterations.)
Furthermore, if there is a length- path from to in the residual network at iteration , then the path must be using only edges which were already present in the residual network at iteration and which were “forward edges” at iteration . This also means that, in all the subsequent iterations in which the distance from to remains , it is so because there is a length- path made entirely of edges that were forward edges at iteration . At each iteration, however, at least one of those edges is saturated and is absent from the residual network in subsequent steps, and so there can be at most iterations during which the distance from to stays .
3. The Push-Relabel Approach
All maximum flow algorithms are based on the maximum flow — minimum cut theorem, which says that if there is no path in the residual network then the flow is optimal. Our goal is thus to “simply” find a flow such that is unreachable from in the residual network.
In algorithms based on the Ford-Fulkerson approach, we keep at every step a feasible flow, and we stop when we reach a step in which there is no path in the residual network.
In algorithms based on the push-relabel method, we take a somewhat complementary approach: at every step we have an assignment of flows to edges which is not a feasible flow (it violates the conservation constraints), which is called a preflow, but for which we can still define the notion of a residual network. The algorithm maintains the condition that, at every step, is not reachable from in the residual network. The algorithm stops when the preflow becomes a feasible flow.
The basic outline of the algorithm is the following: we begin by sending as much flow out of as allowed by the capacities of the edges coming out of , without worrying whether all that flow can actually reach . Then, at each iteration, we consider nodes that have more incoming flow than outgoing flow (initially, the neighbors of ), and we route the excess flow to their neighbors, and so on. The idea is that if we attempted to send too much flow out of in the first step, then the excess will eventually come back to , while will receive the maximum possible flow. To make such an idea work, we need to make sure that we do not keep sending the flow in circles, and that there is a sensible measure of “progress” that we can use to bound the running time of the algorithm.
A main idea in the algorithm is to associate to each vertex a height , with the intuition that the flow wants to go downhill, and we will take the action of sending extra flow from a vertex to a vertex only if . This will help us avoid pushing flow around in circles, and it will help us define a measure of “progress” to bound the running time.
Here is the outline of the algorithm. Given an assignment of flows to each edge , and a vertex , the excess flow at is the quantity
that is, the difference between the flow getting into and the flow getting out of . If is a feasible flow, then the excess flow is always zero, except at and .
- 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
As we said, the algorithm begins by pushing as much flow to the neighbors of as allowed by the capacities of the edges coming out of . This means that we get some vertices with positive excess flow, and some vertices with zero excess flow. Also, we do not violate the capacity constraints. These properties define the notion of a preflow.
Definition 4 (Preflow) An assignment of a non-negative flow to each edge of a network is a preflow if
- for each edge ,
- for each vertex ,
A preflow in which all excess flows are zero for each is a feasible flow.
The definition of residual network for a preflow is the same as for a flow; the capacity of an edge in the residual network is
If the edge has capacity in the residual network corresponding to a preflow , and the vertex has excess flow , then we can send units of flow from to (by increasing and/or reducing ) and create another preflow. In the new preflow, the excess of is units less than before, and the excess flow of is units more than before.
Such a “shifting” of excess flow from one node to another is the basic operation of a push-relabel algorithm, and it is called a push operation. If we push an amount of flow along an edge equal to its capacity in the residual network, then we call it a saturating push, otherwise we call it a nonsaturating push. We execute a push operation provided that we find a pair of vertices such that we can push from a “higher” vertex to a “lower” vertex, according to the height function .
If the above operation is not possible, we take a vertex with excess flow, and we increase its height. This operation is called a relabel operation.
The reader should try running this algorithm by hand on a few examples to get a sense of how it works.
By our discussion so far, it is by no means clear that this algorithm terminates at all. Indeed, in the next lecture we will show that
- Each vertex can reach, at most, height , and so the maximum number of relabel operations that can be executed is ;
- The number of saturating push that can be executed along an edge is at most , and so the total number of saturating push operations that can be executed is at most . (There are up to edges that can appear in the residual networks at various stages.)
- The total number of nonsaturating push operations that can be executed is at most . (This will be the only difficult part of the analysis.)
- Each operation can be executed in constant time.
So overall we have a running time .