|
|
< Day Day Up > |
|
In this section, we present the "push-relabel" approach to computing maximum flows. To date, many of the asymptotically fastest maximum-flow algorithms are push-relabel algorithms, and the fastest actual implementations of maximum-flow algorithms are based on the push-relabel method. Other flow problems, such as the minimum-cost flow problem, can be solved efficiently by push-relabel methods. This section introduces Goldberg's "generic" maximum-flow algorithm, which has a simple implementation that runs in O(V2 E) time, thereby improving upon the O(V E2) bound of the Edmonds-Karp algorithm. Section 26.5 refines the generic algorithm to obtain another push-relabel algorithm that runs in O(V3) time.
Push-relabel algorithms work in a more localized manner than the Ford-Fulkerson method. Rather than examine the entire residual network G = (V, E) to find an augmenting path, push-relabel algorithms work on one vertex at a time, looking only at the vertex's neighbors in the residual network. Furthermore, unlike the Ford-Fulkerson method, push-relabel algorithms do not maintain the flow-conservation property throughout their execution. They do, however, maintain a preflow, which is a function f : V × V → R that satisfies skew symmetry, capacity constraints, and the following relaxation of flow conservation: f(V, u) ≥ 0 for all vertices u ∈ V - {s}. That is, the total net flow at each vertex other than the source is nonnegative. We call the total net flow at a vertex u the excess flow into u, given by
We say that a vertex u ∈ V - {s, t} is overflowing if e(u) > 0.
We shall start this section by describing the intuition behind the push-relabel method. We shall then investigate the two operations employed by the method: "pushing" preflow and "relabeling" a vertex. Finally, we shall present a generic push-relabel algorithm and analyze its correctness and running time.
The intuition behind the push-relabel method is probably best understood in terms of fluid flows: we consider a flow network G = (V, E) to be a system of interconnected pipes of given capacities. Applying this analogy to the Ford-Fulkerson method, we might say that each augmenting path in the network gives rise to an additional stream of fluid, with no branch points, flowing from the source to the sink. The Ford-Fulkerson method iteratively adds more streams of flow until no more can be added.
The generic push-relabel algorithm has a rather different intuition. As before, directed edges correspond to pipes. Vertices, which are pipe junctions, have two interesting properties. First, to accommodate excess flow, each vertex has an out-flow pipe leading to an arbitrarily large reservoir that can accumulate fluid. Second, each vertex, its reservoir, and all its pipe connections are on a platform whose height increases as the algorithm progresses.
Vertex heights determine how flow is pushed: we only push flow downhill, that is, from a higher vertex to a lower vertex. The flow from a lower vertex to a higher vertex may be positive, but operations that push flow only push it downhill. The height of the source is fixed at |V|, and the height of the sink is fixed at 0. All other vertex heights start at 0 and increase with time. The algorithm first sends as much flow as possible downhill from the source toward the sink. The amount it sends is exactly enough to fill each outgoing pipe from the source to capacity; that is, it sends the capacity of the cut (s, V - s). When flow first enters an intermediate vertex, it collects in the vertex's reservoir. From there, it is eventually pushed downhill.
It may eventually happen that the only pipes that leave a vertex u and are not already saturated with flow connect to vertices that are on the same level as u or are uphill from u. In this case, to rid an overflowing vertex u of its excess flow, we must increase its height-an operation called "relabeling" vertex u. Its height is increased to one unit more than the height of the lowest of its neighbors to which it has an unsaturated pipe. After a vertex is relabeled, therefore, there is at least one outgoing pipe through which more flow can be pushed.
Eventually, all the flow that can possibly get through to the sink has arrived there. No more can arrive, because the pipes obey the capacity constraints; the amount of flow across any cut is still limited by the capacity of the cut. To make the preflow a "legal" flow, the algorithm then sends the excess collected in the reservoirs of overflowing vertices back to the source by continuing to relabel vertices to above the fixed height |V| of the source. As we shall see, once all the reservoirs have been emptied, the preflow is not only a "legal" flow, it is also a maximum flow.
From the preceding discussion, we see that there are two basic operations performed by a push-relabel algorithm: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex. The applicability of these operations depends on the heights of vertices, which we now define precisely.
Let G = (V, E) be a flow network with source s and sink t, and let f be a preflow in G. A function h : V → N is a height function[3] if h(s) = |V|, h(t) = 0, and
h(u) ≤ h(v) + 1
for every residual edge (u, v) ∈ Ef. We immediately obtain the following lemma.
 |
Let G = (V, E) be a flow network, let f be a preflow in G, and let h be a height function on V. For any two vertices u, v ∈ V, if h(u) > h(v) + 1, then (u, v) is not an edge in the residual graph.
|
The basic operation PUSH(u, v) can be applied if u is an overflowing vertex, cf (u, v) > 0, and h(u) = h(v) + 1. The pseudocode below updates the preflow f in an implied network G = (V, E). It assumes that residual capacities can also be computed in constant time given c and f. The excess flow stored at a vertex u is maintained as the attribute e[u], and the height of u is maintained as the attribute h[u]. The expression df (u, v) is a temporary variable that stores the amount of flow that can be pushed from u to v.
PUSH(u, v) 1 ▹ Applies when: u is overflowing, cf(u, v) > 0, and h[u] = h[v] + 1. 2 ▹ Action: Push df(u, v) = min(e[u], cf(u, v)) units of flow from u to v. 3 df(u, v) ← min(e[u], cf(u, v)) 4 f[u, v] ← f[u, v] + df(u, v) 5 f[v, u] ← - f[u, v] 6 e[u] ← e[u] - df(u, v) 7 e[v] ← e[v] + df(u, v)
The code for PUSH operates as follows. Vertex u is assumed to have a positive excess e[u], and the residual capacity of (u, v) is positive. Thus, we can we increase the flow from u to v by df(u, v) = min(e[u], cf (u, v)) without causing e[u] to become negative or the capacity c(u, v) to be exceeded. Line 3 computes the value df(u, v), and we update f in lines 4-5 and e in lines 6-7. Thus, if f is a preflow before PUSH is called, it remains a preflow afterward.
Observe that nothing in the code for PUSH depends on the heights of u and v, yet we prohibit it from being invoked unless h[u] = h[v] + 1. Thus, excess flow is pushed downhill only by a height differential of 1. By Lemma 26.13, no residual edges exist between two vertices whose heights differ by more than 1, and thus, as long as the attribute h is indeed a height function, there is nothing to be gained by allowing flow to be pushed downhill by a height differential of more than 1.
We call the operation PUSH(u, v) a push from u to v. If a push operation applies to some edge (u, v) leaving a vertex u, we also say that the push operation applies to u. It is a saturating push if edge (u, v) becomes saturated (cf(u, v) = 0 afterward); otherwise, it is a nonsaturating push. If an edge is saturated, it does not appear in the residual network. A simple lemma characterizes one result of a nonsaturating push.
The basic operation RELABEL (u) applies if u is overflowing and if h[u] ≤ h[v] for all edges (u, v) ∈ Ef. In other words, we can relabel an overflowing vertex u if for every vertex v for which there is residual capacity from u to v, flow cannot be pushed from u to v because v is not downhill from u. (Recall that by definition, neither the source s nor the sink t can be overflowing, so neither s nor t can be relabeled.)
RELABEL(u) 1 ▹ Applies when: u is overflowing and for all v ∈ V such that (u, v) ∈ Ef, we have h[u] ≤ h[v]. 2 ▹ Action: Increase the height of u. 3 h[u] ← 1 + min {h[v] : (u, v) ∈ Ef}
When we call the operation RELABEL(u), we say that vertex u is relabeled. Note that when u is relabeled, Ef must contain at least one edge that leaves u, so that the minimization in the code is over a nonempty set. This property follows from the assumption that u is overflowing. Since e[u] > 0, we have e[u] = f(V, u) > 0, and hence there must be at least one vertex v such that f[v, u] > 0. But then,
|
cf(u, v) |
= |
c(u, v) - f[u, v] |
|
= |
c(u, v) + f[v, u] |
|
|
> |
0, |
which implies that (u, v) ∈ Ef. The operation RELABEL(u) thus gives u the greatest height allowed by the constraints on height functions.
The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network.
INITIALIZE-PREFLOW(G, s) 1 for each vertex u ∈ V[G] 2 do h[u] ← 0 3 e[u] ← 0 4 for each edge (u, v) ∈ E[G] 5 do f[u, v] ← 0 6 f[v, u] ← 0 7 h[s] ← |V[G]| 8 for each vertex u ∈ Adj[s] 9 do f[s, u] ← c(s, u) 10 f[u, s] ← -c(s, u) 11 e[u] ← c(s, u) 12 e[s] ← e[s] - c(s, u)
INITIALIZE-PREFLOW creates an initial preflow f defined by
| (26.10) |  |
That is, each edge leaving the source s is filled to capacity, and all other edges carry no flow. For each vertex v adjacent to the source, we initially have e[v] = c(s, v), and e[s] is initialized to the negative of the sum of these capacities. The generic algorithm also begins with an initial height function h, given by
This is a height function because the only edges (u, v) for which h[u] > h[v] + 1 are those for which u = s, and those edges are saturated, which means that they are not in the residual network.
Initialization, followed by a sequence of push and relabel operations, executed in no particular order, yields the GENERIC-PUSH-RELABEL algorithm:
GENERIC-PUSH-RELABEL(G) 1 INITIALIZE-PREFLOW(G, s) 2 while there exists an applicable push or relabel operation 3 do select an applicable push or relabel operation and perform it
The following lemma tells us that as long as an overflowing vertex exists, at least one of the two basic operations applies.
|
Let G = (V, E) be a flow network with source s and sink t, let f be a preflow, and let h be any height function for f. If u is any overflowing vertex, then either a push or relabel operation applies to it.
Proof For any residual edge (u, v), we have h(u) ≤ h(v)+1 because h is a height function. If a push operation does not apply to u, then for all residual edges (u, v), we must have h(u) < h(v) + 1, which implies h(u) ≤ h(v). Thus, a relabel operation can be applied to u.
|
To show that the generic push-relabel algorithm solves the maximum-flow problem, we shall first prove that if it terminates, the preflow f is a maximum flow. We shall later prove that it terminates. We start with some observations about the height function h.
|
During the execution of GENERIC-PUSH-RELABEL on a flow network G = (V, E), for each vertex u ∈ V, the height h[u] never decreases. Moreover, whenever a relabel operation is applied to a vertex u, its height h[u] increases by at least 1.
Proof Because vertex heights change only during relabel operations, it suffices to prove the second statement of the lemma. If vertex u is about to be relabeled, then for all vertices v such that (u, v) ∈ Ef, we have h[u] ≤ h[v]. Thus, h[u] < 1 + min {h[v] : (u, v) ∈ Ef}, and so the operation must increase h[u].
|
|
Let G = (V, E) be a flow network with source s and sink t. During the execution of GENERIC-PUSH-RELABEL on G, the attribute h is maintained as a height function.
Proof The proof is by induction on the number of basic operations performed. Initially, h is a height function, as we have already observed.
We claim that if h is a height function, then an operation RELABEL(u) leaves h a height function. If we look at a residual edge (u, v) ∈ Ef that leaves u, then the operation RELABEL(u) ensures that h[u] ≤ h[v] + 1 afterward. Now consider a residual edge (w, u) that enters u. By Lemma 26.16, h[w] ≤ h[u] + 1 before the operation RELABEL(u) implies h[w] < h[u] + 1 afterward. Thus, the operation RELABEL(u) leaves h a height function.
Now, consider an operation PUSH(u, v). This operation may add the edge (v, u) to Ef, and it may remove (u, v) from Ef. In the former case, we have h[v] = h[u] - 1 < h[u] + 1, and so h remains a height function. In the latter case,the removal of (u, v) from the residual network removes the corresponding constraint, and h again remains a height function.
|
The following lemma gives an important property of height functions.
|
Let G = (V, E) be a flow network with source s and sink t, let f be a preflow in G, and let h be a height function on V. Then there is no path from the source s to the sink t in the residual network Gf.
Proof Assume for the sake of contradiction that there is a path p = 〈v0, v1, . . . , vk〉 from s to t in Gf, where v0 = s and vk = t. Without loss of generality, p is a simple path, and so k < |V|. For i = 0, 1, . . . , k - 1, edge (vi, vi+1) ∈ Ef. Because h is a height function, h(vi) ≤ h(vi+1) + 1 for i = 0, 1, . . . , k - 1. Combining these inequalities over path p yields h(s) ≤ h(t) + k. But because h(t) = 0, we have h(s) ≤ k < |V|, which contradicts the requirement that h(s) = |V| in a height function.
|
We are now ready to show that if the generic push-relabel algorithm terminates, the preflow it computes is a maximum flow.
|
If the algorithm GENERIC-PUSH-RELABEL terminates when run on a flow network G = (V, E) with source s and sink t, then the preflow f it computes is a maximum flow for G.
Proof We use the following loop invariant:
Each time the while loop test in line 2 in GENERIC-PUSH-RELABEL is executed, f is a preflow.
Initialization: INITIALIZE-PREFLOW makes f a preflow.
Maintenance: The only operations within the while loop of lines 2-3 are push and relabel. Relabel operations affect only height attributes and not the flow values; hence they do not affect whether f is a preflow. As argued on page 672, if f is a preflow prior to a push operation, it remains a preflow afterward.
Termination: At termination, each vertex in V - {s, t} must have an excess of 0, because by Lemmas 26.15 and 26.17 and the invariant that f is always a preflow, there are no overflowing vertices. Therefore, f is a flow. Because h is a height function, Lemma 26.18 tells us that there is no path from s to t in the residual network Gf. By the max-flow min-cut theorem (Theorem 26.7), therefore, f is a maximum flow.
|
To show that the generic push-relabel algorithm indeed terminates, we shall bound the number of operations it performs. Each of the three types of operations-relabels, saturating pushes, and nonsaturating pushes-is bounded separately. With knowledge of these bounds, it is a straightforward problem to construct an algorithm that runs in O(V2E) time. Before beginning the analysis, however, we prove an important lemma.
|
Let G = (V, E) be a flow network with source s and sink t, and let f be a preflow in G. Then, for any overflowing vertex u, there is a simple path from u to s in the residual network Gf.
Proof For an overflowing vertex u, let U = {v: there exists a simple path from u to v in Gf}, and suppose for the sake of contradiction that s ∉ U. Let Ū = V - U.
We claim for each pair of vertices w ∈ Ū and v ∈ U that f(w, v) ≤ 0. Why? If f(w, v) > 0, then f(v, w) < 0, which in turn implies that cf(v, w) = c(v, w) - f(v, w) > 0. Hence, there exists an edge (v, w) ∈ Ef, and therefore a simple path of the form 
in Gf, contradicting our choice of w.
Thus, we must have f(Ū, U) ≤ 0, since every term in this implicit summation is nonpositive, and hence
|
e(U) |
= |
f(V, U) |
(by equation (26.9)) |
|
= |
f(Ū, U) + f(U, U) |
(by Lemma 26.1, part (3)) |
|
|
= |
f(Ū, U) |
(by Lemma 26.1, part (1)) |
|
|
≤ |
0. |
Excesses are nonnegative for all vertices in V -{s}; because we have assumed that U ⊆ V -{s}, we must therefore have e(v) = 0 for all vertices v ∈ U. In particular, e(u) = 0, which contradicts the assumption that u is overflowing.
|
The next lemma bounds the heights of vertices, and its corollary bounds the number of relabel operations that are performed in total.
|
Let G = (V, E) be a flow network with source s and sink t. At any time during the execution of GENERIC-PUSH-RELABEL on G, we have h[u] ≤ 2 |V| - 1 for all vertices u ∈ V.
Proof The heights of the source s and the sink t never change because these vertices are by definition not overflowing. Thus, we always have h[s] = |V| and h[t] = 0, both of which are no greater than 2 |V | - 1.
Now consider any vertex u ∈ V -{s, t}. Initially, h[u] = 0 ≤ 2 |V|-1. We shall show that after each relabeling operation, we still have h[u] ≤ 2 |V|-1. When u is relabeled, it is overflowing, and Lemma 26.20 tells us that there is a simple path p from u to s in Gf. Let p = 〈v0, v1, . . . ,vk〉, where v0 = u, vk = s, and k ≤ |V|-1 because p is simple. For i = 0, 1, . . . , k - 1, we have (vi, vi+1) ∈ Ef, and therefore, by Lemma 26.17, h[vi] ≤ h[vi+1] + 1. Expanding these inequalities over path p yields h[u] = h[v0] ≤ h[vk] + k ≤ h[s] + (|V| - 1) = 2 |V| - 1.
|
|
Let G = (V, E) be a flow network with source s and sink t. Then, during the execution of GENERIC-PUSH-RELABEL on G, the number of relabel operations is at most 2 |V| - 1 per vertex and at most (2 |V| - 1)|V| - 2) < 2 |V|2 overall.
Proof Only the |V|-2 vertices in V -{s, t} may be relabeled. Let u ∈ V -{s, t}. The operation RELABEL(u) increases h[u]. The value of h[u] is initially 0 and by Lemma 26.21 grows to at most 2 |V| - 1. Thus, each vertex u ∈ V - {s, t} is relabeled at most 2 |V| - 1 times, and the total number of relabel operations performed is at most (2 |V| - 1)(|V| - 2) < 2 |V|2.
|
Lemma 26.21 also helps us to bound the number of saturating pushes.
|
During the execution of GENERIC-PUSH-RELABEL on any flow network G = (V, E), the number of saturating pushes is less than 2 |V||E|.
Proof For any pair of vertices u, v ∈ V, we will count the saturating pushes from u to v and from v to u together, calling them the saturating pushes between u and v. If there are any such pushes, at least one of (u, v) and (v, u) is actually an edge in E. Now, suppose that a saturating push from u to v has occurred. At that time, h[v] = h[u] - 1. In order for another push from u to v to occur later, the algorithm must first push flow from v to u, which cannot happen until h[v] = h[u] + 1. Since h[u] never decreases, in order for h[v] = h[u] + 1, the value of h[v] must increase by at least 2. Likewise, h[u] must increase by at least 2 between saturating pushes from v to u. Heights start at 0 and, by Lemma 26.21, never exceed 2 |V|- 1, which implies that the number of times any vertex can have its height increase by 2 is less than |V|. Since at least one of h[u] and h[v] must increase by 2 between any two saturating pushes between u and v, there are fewer than 2 |V| saturating pushes between u and v. Multiplying by the number of edges gives a bound of less than 2 |V||E| on the total number of saturating pushes.
|
The following lemma bounds the number of nonsaturating pushes in the generic push-relabel algorithm.
|
During the execution of GENERIC-PUSH-RELABEL on any flow network G = (V, E), the number of nonsaturating pushes is less than 4 |V|2 (|V| + |E|).
Proof Define a potential function Φ = Σv:e(v)>0h[v]. Initially, Φ= 0, and the value of Φ may change after each relabeling, saturating push, and nonsaturating push. We will bound the amount that saturating pushes and relabelings can contribute to the increase of Φ. Then we will show that each nonsaturating push must decrease Φ by at least 1, and will use these bounds to derive an upper bound on the number of nonsaturating pushes.
Let us examine the two ways in which Φ might increase. First, relabeling a vertex u increases Φ by less than 2 |V|, since the set over which the sum is taken is the same and the relabeling cannot increase u's height by more than its maximum possible height, which, by Lemma 26.21, is at most 2 |V|- 1. Second, a saturating push from a vertex u to a vertex v increases Φ by less than 2 |V|, since no heights change and only vertex v, whose height is at most 2 |V| - 1, can possibly become overflowing.
Now we show that a nonsaturating push from u to v decreases Φ by at least 1. Why? Before the nonsaturating push, u was overflowing, and v may or may not have been overflowing. By Lemma 26.14, u is no longer overflowing after the push. In addition, v must be overflowing after the push, unless it is the source. Therefore, the potential function Φ has decreased by exactly h[u], and it has increased by either 0 or h[v]. Since h[u] - h[v] = 1, the net effect is that the potential function has decreased by at least 1.
Thus, during the course of the algorithm, the total amount of increase in Φ is due to relabelings and saturated pushes and is constrained by Corollary 26.22 and Lemma 26.23 to be less than (2 |V|)(2 |V|2) + (2 |V|)(2 |V||E|) = 4 |V|2 (|V| + |E|). Since Φ ≥ 0, the total amount of decrease, and therefore the total number of nonsaturating pushes, is less than 4 |V|2 (|V| + |E|).
|
Having bounded the number of relabelings, saturating pushes, and nonsaturating push, we have set the stage for the following analysis of the GENERIC-PUSH-RELABEL procedure, and hence of any algorithm based on the push-relabel method.
|
During the execution of GENERIC>-PUSH-RELABEL on any flow network G = (V, E), the number of basic operations is O(V2E).
Proof Immediate from Corollary 26.22 and Lemmas 26.23 and 26.24.
|
Thus, the algorithm terminates after O(V2 E) operations. All that remains is to give an efficient method for implementing each operation and for choosing an appropriate operation to execute.
|
There is an implementation of the generic push-relabel algorithm that runs in O(V2 E) time on any flow network G = (V, E).
Proof Exercise 26.4-1 asks you to show how to implement the generic algorithm with an overhead of O(V) per relabel operation and O(1) per push. It also asks you to design a data structure that allows you to pick an applicable operation in O(1) time. The corollary then follows.
|
|
Show how to implement the generic push-relabel algorithm using O(V) time per relabel operation, O(1) time per push, and O(1) time to select an applicable operation, for a total time of O(V2E).
|
|
Prove that the generic push-relabel algorithm spends a total of only O(V E) time in performing all the O(V2) relabel operations.
|
|
Suppose that a maximum flow has been found in a flow network G = (V, E) using a push-relabel algorithm. Give a fast algorithm to find a minimum cut in G.
|
|
Give an efficient push-relabel algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm.
|
|
Suppose that all edge capacities in a flow network G = (V, E) are in the set {1, 2, . . . , k}. Analyze the running time of the generic push-relabel algorithm in terms of |V|, |E|, and k. (Hint: How many times can each edge support a nonsaturating push before it becomes saturated?)
|
|
Show that line 7 of INITIALIZE-PREFLOW can be changed to
7 h[s] ← |V[G]| - 2
without affecting the correctness or asymptotic performance of the generic push-relabel algorithm.
|
|
Let δf (u, v) be the distance (number of edges) from u to v in the residual network Gf. Show that GENERIC-PUSH-RELABEL maintains the properties that h[u] < |V| implies h[u] ≤ δf(u, t) and that h[u] ≥ |V| implies h[u] -|V| ≤ δf(u, s).
|
|
As in the previous exercise, let δf(u, v) be the distance from u to v in the residual network Gf. Show how the generic push-relabel algorithm can be modified to maintain the property that h[u] < |V| implies h[u] = δf(u, t) and that h[u] ≥ |V| implies h[u] - |V| = δf(u, s). The total time that your implementation dedicates to maintaining this property should be O(V E).
|
|
Show that the number of nonsaturating pushes executed by GENERIC-PUSH-RELABEL on a flow network G = (V, E) is at most 4 |V|2|E| for |V| ≥ 4.
|
[3]In the literature, a height function is typically called a "distance function," and the height of a vertex is called a "distance label." We use the term "height" because it is more suggestive of the intuition behind the algorithm. We retain the use of the term "relabel" to refer to the operation that increases the height of a vertex. The height of a vertex is related to its distance from the sink t, as would be found in a breadth-first search of the transpose GT.
|
|
< Day Day Up > |
|
