Push–Relabel Algorithm

Push–relabel algorithm (also known as the preflow–push algorithm or the Goldberg–Tarjan algorithm) is a foundational family of strongly polynomial algorithms in computation and algorithms for solving the maximum-flow and minimum s–t cut problems in directed capacitated networks. Formulated by Andrew V. Goldberg and Robert E. Tarjan in 1986 (journal publication 1988), building upon Alexander Karzanov's 1974 layered preflow concept, the method departs from path-augmentation paradigms such as the Ford–Fulkerson algorithm and Dinic's algorithm.

Instead of maintaining flow conservation at every internal vertex and searching globally for source-to-sink paths in the residual network, the push–relabel algorithm relaxes conservation to allow a preflow in which incoming flow at a vertex u may exceed outgoing flow, creating a non-negative excess e(u) ≥ 0. Each vertex is assigned an integer height (or distance label) d(u), and flow excess is moved locally along individual admissible edges satisfying d(u) = d(v) + 1 via push operations or elevated when locally blocked via relabel operations. Depending on the active-vertex selection rule, the algorithm runs in O(V²E) generic time, O(V³) with first-in first-out (FIFO) queues, O(V² √E) under the highest-label selection rule, and O(V E log(V²/E)) when accelerated by a link/cut tree.

Preflows and Vertex Excess

Let G = (V, E, c) be a directed flow network with source s ∈ V, sink t ∈ V, vertex count V = |V|, and edge count E = |E|. A preflow is a real-valued function f : V × V → ℝ that satisfies three conditions:

1. Capacity Constraint: For all (u, v) ∈ V × V, f(u, v) ≤ c(u, v).
2. Skew Symmetry: For all (u, v) ∈ V × V, f(u, v) = −f(v, u).
3. Non-Negative Excess (Relaxed Conservation): For every vertex u ∈ V \ {s}, the net incoming flow—termed the excess e(u)—is non-negative:

An internal vertex u ∈ V \ {s, t} with strictly positive excess e(u) > 0 is called active (or overflowing). When no active vertices remain (e(u) = 0 for all u ∈ V \ {s, t}), the preflow satisfies Kirchhoff flow conservation everywhere and is a valid flow.

Valid Height Labeling and Absence of Augmenting Paths

To guide excess flow toward the sink t—and return unroutable excess back to the source s—the algorithm maintains a height function (or valid distance labeling) d : V → ℤ_≥0 satisfying two invariants with respect to the residual network G_f = (V, E_f), where c_f(u, v) = c(u, v) − f(u, v) > 0:

1. Boundary Conditions: d(s) = V and d(t) = 0.
2. Steepness Invariant: For every residual edge (u, v) ∈ E_f,

A residual edge (u, v) ∈ E_f is called admissible if d(u) = d(v) + 1 (meaning it steps downward by 1 unit of height). The steepness invariant immediately implies a key structural theorem within computational complexity theory: if d is a valid height labeling for preflow f, then no augmenting path from s to t exists in G_f. Indeed, any simple s–t path p in G_f has at most V − 1 edges, so summing d(u) − d(v) ≤ 1 along p yields d(s) − d(t) ≤ V − 1, contradicting d(s) − d(t) = V − 0 = V. Consequently, as soon as all active vertices are eliminated (e(u) = 0 for all u ∈ V \ {s, t}), the resulting valid flow f is guaranteed to be a maximum flow.

Initialization, Push, and Relabel Operations

The algorithm initializes the preflow by saturating every edge leaving the source: f(s, v) = c(s, v) for all (s, v) ∈ E, and f(u, v) = 0 elsewhere. It sets d(s) = V and d(v) = 0 for all v ∈ V \ {s}. Because every outgoing source edge is saturated and removed from E_f, no residual edge leaves s, so d(u) ≤ d(v) + 1 holds everywhere at initialization. Thereafter, while any active vertex u ∈ V \ {s, t} with e(u) > 0 exists, the algorithm executes one of two local primitives:

• Push(u, v): Applicable when u is active (e(u) > 0), c_f(u, v) > 0, and d(u) = d(v) + 1. Push Δ = min(e(u), c_f(u, v)) units of flow from u to v, updating f(u, v) ← f(u, v) + Δ, e(u) ← e(u) − Δ, and e(v) ← e(v) + Δ.
  • A push is saturating if Δ = c_f(u, v) (removing (u, v) from E_f).
  • A push is non-saturating if Δ = e(u) < c_f(u, v) (reducing e(u) to 0 and deactivating u).
• Relabel(u): Applicable when u is active (e(u) > 0) and no outgoing residual edge (u, v) ∈ E_f satisfies d(u) = d(v) + 1 (so d(u) ≤ d(v) for all (u, v) ∈ E_f). Increase u's height to the highest value compatible with the steepness invariant:

Bounding Relabels, Saturating Pushes, and Non-Saturating Pushes

Goldberg and Tarjan established four fundamental counting bounds that govern every variant of the push–relabel method:

1. Maximum Vertex Height (d(u) ≤ 2V − 1): For every active vertex u (e(u) > 0), Flow Decomposition implies there exists a simple path in G_f from u back to the source s. Since that simple path has at most V − 1 edges and d(s) = V, the steepness invariant bounds d(u) ≤ d(s) + (V − 1) = 2V − 1.
2. Total Relabel Operations (O(V²)): Because d(u) starts at 0, increases by at least 1 on every relabel, and never exceeds 2V − 1, each vertex u ∈ V \ {s, t} is relabeled at most 2V − 1 times, giving at most (2V − 1)(V − 2) < 2V² relabels in total (taking O(V E) total scan time).
3. Total Saturating Pushes (O(V E)): After a saturating push on (u, v) where d(u) = d(v) + 1, (u, v) disappears from E_f until a push occurs in the reverse direction (v, u), which requires d(v) = d(u) + 1 (so d(v) must increase by at least 2). Before another saturating push on (u, v) can occur, d(u) must also increase by at least 2. Since d(u) + d(v) ≤ 4V − 2, each edge experiences at most V saturating pushes, giving at most V E saturating pushes across all edges.
4. Total Non-Saturating Pushes (O(V²E) Generic): Using the potential function Φ = ∑_{u active} d(u), every non-saturating push decreases Φ by at least 1, whereas relabels and saturating pushes increase Φ by at most 2V² + 2V²E, bounding generic non-saturating pushes by O(V²E).

Selection Rules and Practical Heuristics

In practical implementations (such as Cherkassky and Goldberg's HIPR solver), two periodically executed heuristics accelerate convergence by one to two orders of magnitude:

• Global Relabeling Heuristic: Periodically run a backward BFS in G_f from t (assigning exact shortest residual distances d(u) = dist_Gf(u, t)) and from s (assigning V + dist_Gf(u, s)), jumping over hundreds of incremental local relabels.
• Gap Relabeling Heuristic: If at any step there is an integer height 0 < g < V such that no vertex has height d(u) = g, then no vertex with g < d(v) < V can reach t in G_f; all such vertices v have their height updated to d(v) ← max(d(v), V + 1) in O(1) amortized time per vertex.

The highest-label push–relabel algorithm is the standard industrial solver for dense maximum-flow and minimum-cut instances, including Hao–Orlin global minimum cut, parametric minimum cut in portfolio optimization and open-pit mine scheduling, 3D volumetric medical image segmentation, and Gomory–Hu tree construction in bioinformatics.

How is the minimum s–t cut extracted from a push–relabel execution?

Even before returning excess flow back to the source s (during the first phase when t is no longer reachable from any active vertex), the gap height g (or a single backward BFS from t in G_f) partitions V into T (vertices that can reach t in G_f) and S = V \ T, which forms an optimal minimum s–t cut.

Why is highest-label selection faster than FIFO selection on sparse graphs?

Always discharging the active vertex u with maximum height d(u) consolidates excess packets at high levels before pushing them downward together, reducing the number of non-saturating pushes from O(V³) to O(V² √E), as proved by Joseph Cheriyan and S. N. Maheshwari (1989) and tuned by Boris Cherkassky and Andrew Goldberg (1997).

1. Goldberg, A. V., & Tarjan, R. E. (1988). "A new approach to the maximum-flow problem." Journal of the ACM, 35(4), 921–940. https://doi.org/10.1145/48014.61051
2. Karzanov, A. V. (1974). "Determining the maximal flow in a network by the method of preflows." Soviet Mathematics Doklady, 15, 434–437. https://mathscinet.ams.org/mathscinet-getitem?mr=0349218
3. Cheriyan, J., & Maheshwari, S. N. (1989). "Analysis of preflow push algorithms for maximum network flow." SIAM Journal on Computing, 18(6), 1057–1086. https://doi.org/10.1137/0218072
4. Cherkassky, B. V., & Goldberg, A. V. (1997). "On implementing the push–relabel method for the maximum flow problem." Algorithmica, 19(4), 390–410. https://doi.org/10.1007/PL00009180