Push-relabel Algorithms
Push-relabel algorithms: 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.
Intuition: 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.
The basic operations: 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 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.
The push operation: 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)