In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink. The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial O(V 2E) time complexity, which is asymptotically more efficient than the O(VE 2) Edmonds–Karp algorithm. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has O(V 2√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic O(VElog(V 2/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient. The push–relabel algorithm has been extended to compute minimum cost flows. The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance.
History A preflow is a flow in which the total amount flowing into a vertex may be greater than the total amount flowing out of it, allowing an algorithm to change the flow on a single arc. This idea was originally conceived by Alexander V. Karzanov and was published in 1974 in Soviet Mathematical Dokladi 15. This pre-flow algorithm also used a push operation; however, it used distances in the auxiliary network to determine where to push the flow instead of a labeling system. The push-relabel algorithm was designed by Andrew V. Goldberg and Robert Tarjan. The algorithm was initially presented in November 1986 in STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, and then officially in October 1988 as an article in the Journal of the ACM. Both papers detail a generic form of the algorithm terminating in O(V 2E) along with a O(V 3) sequential implementation, a O(VE log(V 2/E)) implementation using dynamic trees, and parallel/distributed implementation. As explained in, Goldberg–Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and Uzi Vishkin.
Concepts
Definitions and notations
Let:
G = (V, E) be a network with capacity function c: V × V → ℝ∞, F = (G, c, s, t) a flow network, where s ∈ V and t ∈ V (with s ≠ t) are chosen source and sink vertices respectively, f : V × V → ℝ denote a pre-flow in F, xf : V → ℝ denote the excess function with respect to the flow f, defined by xf (u) = Σv ∈ V f (v, u) − Σv ∈ V f (u, v), cf : V × V → ℝ∞ denote the residual capacity function with respect to the flow f, defined by cf (e) = c(e) − f (e), Ef ⊂ E being the edges where f < c, and
Gf (V, Ef ) denote the residual network of G with respect to the flow f. The push–relabel algorithm uses a nonnegative integer valid labeling function which makes use of distance labels, or heights, on nodes to determine which arcs should be selected for the push operation. This labeling function is denoted by 𝓁 : V → ℕ. This function must satisfy the following conditions in order to be considered valid:
Valid labeling: 𝓁(u) ≤ 𝓁(v) + 1 for all (u, v) ∈ Ef Source condition: 𝓁(s) = | V | Sink conservation: 𝓁(t) = 0 In the algorithm, the label values of s and t are fixed. 𝓁(u) is a lower bound of the unweighted distance from u to t in Gf if t is reachable from u. If u has been disconnected from t, then 𝓁(u) − | V | is a lower bound of the unweighted distance from u to s. As a result, if a valid labeling function exists, there are no s-t paths in Gf because no such paths can be longer than | V | − 1. An arc (u, v) ∈ Ef is called admissible if 𝓁(u) = 𝓁(v) + 1. The admissible network G̃f (V, Ẽf ) is composed of the set of arcs e ∈ Ef that are admissible. The admissible network is acyclic. For a fixed flow f, a vertex v ∉ {s, t} is called active if it has positive excess with respect to f, i.e., xf (u) > 0.
Operations
Initialization The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs (s, v) exiting the source, where v ∈ V \ {s}. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph, 𝓁(s) = | V |, and all other nodes are given a label of zero. Once the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.
Push The push operation applies on an admissible out-arc (u, v) of an active node u in Gf. It moves min{xf (u), cf (u,v)} units of flow from u to v.
push(u, v): assert xf[u] > 0 and 𝓁[u] == 𝓁[v] + 1 Δ = min(xf[u], c[u][v] - f[u][v]) f[u][v] += Δ f[v][u] -= Δ xf[u] -= Δ xf[v] += Δ
A push operation that causes f (u, v) to reach c(u, v) is called a saturating push since it uses up all the available capacity of the residual arc. Otherwise, all of the excess at the node is pushed across the residual arc. This is called an unsaturating or non-saturating push.
Relabel The relabel operation applies on an active node u which is neither the source nor the sink without any admissible out-arcs in Gf. It modifies 𝓁(u) to be the minimum value such that an admissible out-arc is created. Note that this always increases 𝓁(u) and never creates a steep arc, which is an arc (u, v) such that cf (u, v) > 0, and 𝓁(u) > 𝓁(v) + 1.
relabel(u): assert xf[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that cf[u][v] > 0 𝓁[u] = 1 + min(𝓁[v] for all v such that cf[u][v] > 0)
… excerpt ends here. Continue reading the full article.
