Push–relabel maximum flow algorithm

The push–relabel algorithm, also called the preflow–push algorithm, solves the maximum flow problem. It works by keeping a preflow—where flow into a node can exceed flow out—and gradually turning it into a maximum flow. This is done through two main operations: pushing flow locally between neighboring nodes, and relabeling nodes to maintain an admissible network that guides the pushes. Unlike the Ford–Fulkerson algorithm, which sends flow along entire source-to-sink paths, push–relabel works locally.

This algorithm is regarded as one of the most efficient for maximum flow. The generic version has a strongly polynomial time complexity of O(V²E), which is asymptotically better than the O(VE²) of the Edmonds–Karp algorithm. Some variants achieve even lower complexities. The highest-label variant runs in O(V²√E) and is often considered the benchmark for maximum flow algorithms. Using dynamic trees, subcubic O(VE log(V²/E)) complexity is possible, though this is less efficient in practice.

The push–relabel approach has also been extended to compute minimum cost flows. The distance labels it introduced led to a more efficient augmenting path algorithm, which can then be incorporated back into push–relabel to create a variant with better empirical performance.

The concept of a preflow, which allows flow to accumulate at nodes, was first proposed by Alexander V. Karzanov in 1974. His algorithm also used a push operation but relied on distances in an auxiliary network rather than a labeling system.

The push–relabel algorithm itself was designed by Andrew V. Goldberg and Robert Tarjan. It was first presented in November 1986 at STOC '86 and later published in the Journal of the ACM in October 1988. Both papers describe a generic form that terminates in O(V²E), along with a sequential O(V³) implementation, an O(VE log(V²/E)) version using dynamic trees, and parallel or distributed implementations. Goldberg and Tarjan introduced distance labels by adapting them from the parallel maximum flow algorithm of Yossi Shiloach and Uzi Vishkin.

The algorithm uses a valid labeling function that assigns nonnegative integer heights to nodes. This labeling must satisfy: for every residual arc (u, v), the height of u is at most the height of v plus one; the source has height equal to the number of nodes; and the sink has height zero. These labels give a lower bound on the unweighted distance from a node to the sink in the residual network, or to the source if the sink is unreachable. If a valid labeling exists, no source-to-sink path can exist in the residual network. An arc is called admissible if the height of u equals the height of v plus one. The set of admissible arcs forms an acyclic network. A node other than the source or sink is active if it has positive excess flow.

The algorithm begins by initializing the residual graph, setting all preflow values to zero, and saturating all arcs leaving the source. The source is labeled with the total number of nodes, and all other nodes are labeled zero. Then it repeatedly applies push or relabel operations to active nodes until none remain.

A push operation moves flow from an active node u along an admissible outgoing residual arc (u, v). The amount moved is the smaller of u’s excess and the arc’s residual capacity. A saturating push uses up the entire residual capacity; a non-saturating push clears all excess from u.

A relabel operation applies to an active node (not the source or sink) that has no admissible outgoing arcs. It increases the node’s label to the smallest value that creates at least one admissible outgoing arc, ensuring no steep arcs (where residual capacity exists and the label difference is greater than one) are created.