10 Push Relabel Algorithm

The chapter introduces the Push-Relabel approach as a faster, more local alternative to classic augmenting-path max-flow methods. Instead of repeatedly searching the whole graph for source-to-sink paths, it treats the network like a set of connected reservoirs: the source is flooded first, intermediate nodes may temporarily hold excess flow, and flow is guided by a height function that enforces a downhill-only movement rule. This framing makes maximum flow feel less like global route planning and more like local pressure balancing.

The core mechanics are built around three ideas: preflow, excess, and relabeling. A preflow saturates edges leaving the source, creating active nodes with surplus flow that must be drained. Each active node tries to push flow only to neighbors with residual capacity and strictly lower height; if no such neighbor exists, the node is relabeled upward just enough to create a valid downhill edge. The worked example on a small four-node graph shows how repeated push and relabel operations move flow forward, sometimes back along reverse edges, until all intermediate nodes become balanced and the sink holds the full maximum flow.

The chapter also connects the algorithm to real applications and implementation details. It highlights uses such as baseball elimination, open-pit mining, and general-purpose graph libraries, where Push-Relabel is valued for its strong practical performance on dense networks. The summary of complexity notes a generic O(V³) time bound, improved by heuristics in practice, with O(V²) or O(V+E) space depending on the representation. The main takeaway is that local height adjustments and excess draining provide a deterministic, scalable way to solve max-flow and reveal the corresponding minimum cut.

Source (s) connects to Node 1 (capacity 10) and Node 2 (capacity 5). Node 1 connects to Node 2 (capacity 15) and to Sink t (capacity 10). Node 2 connects to Sink t (capacity 10). The notations ‘h’ and ‘e’ denote the height of the vertex and the excess capacity of the vertex it can hold respectively.

State after Iteration 1, Node 1 relabels to height 1 and pushes its full excess of 10 units to Node 2, leaving Node 2 with 15 total excess.

State after Iteration 2, Node 2 relabels to height 1, saturates edge 2 → 3 with 10 units, relabels to height 2, and pushes its remaining 5 units back to Node 1.

Final State is Node 1 pushing its remaining 5 units directly to Sink 3. All intermediate nodes reach zero excess, yielding a maximum network flow of 15.

• The Push-Relabel algorithm computes the maximum flow across a directed capacity graph without searching for global augmenting paths.
• Unlike classical methods that enforce strict flow conservation at every intermediate step, Push-Relabel allows intermediate vertices to temporarily buffer excess flow (e(u) > 0).
• The algorithm eliminates the need to perform expensive, end-to-end graph traversals (such as Breadth-First Search) by replacing global path searches with atomic, vertex-level operations.
• It operates by flooding the graph with a preflow out of the source and iteratively clearing node excess through localized push and relabel operations.
• During initialization, every outgoing edge from the source is saturated to its maximum capacity, depositing initial excess across adjacent intermediate nodes.
• An active vertex u can push excess flow to an adjacent vertex v if and only if positive residual capacity exists and the elevation follows a strict unit downward slope.
• When an active vertex holds excess flow but cannot push downhill to any residual neighbor, a relabel operation raises its elevation to h(u) = min{h(v) | cf(u,v) >0 } + 1.
• Node heights never decrease during execution, they increase strictly through relabel operations, preventing cycle oscillations and ensuring deterministic termination.
• The algorithm terminates when the active set is completely empty, meaning all intermediate vertices have drained their excess to exactly zero and all remaining flow has reached the sink or returned to the source.
• Generic Push-Relabel runs in O(V3) time complexity, outperforming classical O(V2√E) path-based algorithms on dense graphs. Advanced implementations using the Highest-Label heuristic achieve O(V2√E) performance.
• Space complexity is O(V2) when implemented with static 2D capacity/flow matrices, or O(V+E) with adjacency lists.
• Used to evaluate multi-team mathematical elimination in sports analytics by modeling remaining head-to-head match schedules as dense flow networks.
• Solves the maximal closure problem in open-pit mine design to establish optimal 3D extraction boundaries under geotechnical slope constraints.
• Shipped as the standard, production-grade flow solver inside major graph libraries including the Boost Graph Library (push_relabel_max_flow), and NetworkX (preflow_push).

1. Code implementation: https://github.com/aniketwattamwar/Algorithms-Every-Programmer-Should-Know
2. Video Explanation: https://youtu.be/MG_EIgDEuQA?si=m71iIrbdLjufGL9Z
3. Overview of the flow formulation in modern mine-planning practice: "A maximum flow formulation of a multi-period open-pit mining problem," Operational Research (Springer): https://link.springer.com/article/10.1007/s12351-013-0140-7
4. Wayne, K. "A New Property and a Faster Algorithm for Baseball Elimination." SIAM Journal on Discrete Mathematics, 2001. https://epubs.siam.org/doi/10.1137/S0895480198348847 (PDF: https://www.cs.princeton.edu/~wayne/papers/baseball.pdf)
5. Boost Graph Library, "Push-Relabel Maximum Flow": https://www.boost.org/doc/libs/1_87_0/libs/graph/doc/push_relabel_max_flow.html
6. NetworkX, preflow_push documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.preflow_push.html

FAQ