Chapter 10: Push Relabel Algorithm
Introduces maximum network flow as a capacity problem and motivates Push-Relabel’s local approach over repeated global path searches.
After this chapter you will be able to
- Capacity Versus Distance Networks. Distinguish finding maximum source-to-sink throughput in a capacity network from finding shortest paths using static distances or costs.
- Local Operations Instead of Paths. Explain why the introduction motivates Push-Relabel as an alternative to repeated global augmenting-path searches, without describing mechanics not yet taught.
- Local preflow approach. Explain how push-relabel differs from repeatedly finding complete source-to-sink paths: it permits temporary excess at intermediate nodes and makes local decisions to drain it.
- Source preflow initialization. Describe how the four-node example initializes heights and saturates outgoing source edges, and identify which intermediate nodes become active.
- Push and relabel rules. State when an active node can push flow, how much it can push, and what relabeling does when no eligible push is available.
- Reverse-edge rerouting trace. Trace how the example handles node 2’s remaining excess after its edge to the sink fills, and explain why the final sink flow is 15.
- Baseball elimination flow network. Trace how remaining games and team win limits become a flow network, and explain how its maximum flow determines whether the team being tested is eliminated.
- Mining block profit network. Describe how positive- and negative-value mining blocks are represented in the section's flow network and what planning decision it supports.
- Push-Relabel library backends. Explain how production libraries expose Push-Relabel and why it is maintained as a backend.
- Time and storage bounds. State the generic time bound, the improved bounds given for highest-label selection, and how storage depends on the graph representation.
- Local processing with excess flow. Explain how Push–Relabel replaces global path traversal with neighbor-based operations and why intermediate nodes may temporarily hold excess flow.
- Height growth and termination. Explain how increasing, bounded heights limit relabeling and prevent an infinite processing loop.
What it builds on
- All-pairs shortest path (APSP) (chapter 9) · The earlier all-pairs shortest-path problem used here for contrast.
- Graphs (chapter 1) · Assumes familiarity with graphs made of nodes and edges.
Section by section
Introduction
Introduces maximum network flow as a capacity problem and motivates Push-Relabel’s local approach over repeated global path searches.
- Capacity Versus Distance Networks: Distinguish finding maximum source-to-sink throughput in a capacity network from finding shortest paths using static distances or costs.
Why it matters: It identifies the different question this chapter’s algorithm is meant to answer. - Local Operations Instead of Paths: Explain why the introduction motivates Push-Relabel as an alternative to repeated global augmenting-path searches, without describing mechanics not yet taught.
Why it matters: It explains the motivation for shifting from path searches to local node operations.
Key terms: maximum flow, carrying capacities, source, sink, global augmenting paths, Push-Relabel algorithm, localized
10.1 The mechanics of maximum network flow
The section traces push-relabel on a four-node network, showing how temporary excess, local pushes, relabeling, and reverse residual edges produce a maximum flow without repeated end-to-end path searches.
- Local preflow approach: Explain how push-relabel differs from repeatedly finding complete source-to-sink paths: it permits temporary excess at intermediate nodes and makes local decisions to drain it.
Why it matters: Temporary excess is what lets the algorithm work through local decisions rather than search for a complete route each time. - Source preflow initialization: Describe how the four-node example initializes heights and saturates outgoing source edges, and identify which intermediate nodes become active.
Why it matters: Initialization creates the excess that the rest of the algorithm must drain. - Push and relabel rules: State when an active node can push flow, how much it can push, and what relabeling does when no eligible push is available.
Why it matters: These two local rules determine every move in the worked example. - Reverse-edge rerouting trace: Trace how the example handles node 2’s remaining excess after its edge to the sink fills, and explain why the final sink flow is 15.
Why it matters: The backtrack shows how local corrections can redirect flow when a forward edge is saturated. - Active-node queue driver: Describe the implementation-level role of the active-node queue in continuing push and relabel operations.
Why it matters: The queue connects the local operations to an overall stopping condition.
Key terms: preflow, excess, conservation of flow, local decisions, source height, saturate, active node, residual capacity, height, push
10.2 Real-world applications
The section shows how maximum flow is used to test baseball elimination, plan profitable open-pit mines, and power graph-library backends.
- Baseball elimination flow network: Trace how remaining games and team win limits become a flow network, and explain how its maximum flow determines whether the team being tested is eliminated.
Why it matters: The flow test captures constraints between rivals that a simple comparison of win totals misses. - Elimination ranking shortcut: Explain the stated monotonicity shortcut for testing multiple teams in a division.
Why it matters: The ranking result can avoid repeating the elimination flow test for every team. - Mining block profit network: Describe how positive- and negative-value mining blocks are represented in the section's flow network and what planning decision it supports.
Why it matters: It shows how an economic planning problem can be expressed using flow capacities. - Push-Relabel library backends: Explain how production libraries expose Push-Relabel and why it is maintained as a backend.
Why it matters: Application developers can use maximum-flow functionality without implementing Push-Relabel themselves.
Key terms: game-pair node, maximum flow, W − wᵢ, eliminated, structural monotonicity property, maximum achievable win totals, open pit mining, ultimate-pit-limit design, net economic value, positive-profit block
10.3 Key Insights
This section summarizes Push–Relabel’s complexity, local-flow design, termination argument, minimum-cut interpretation, and active-node scheduling choices.
- Time and storage bounds: State the generic time bound, the improved bounds given for highest-label selection, and how storage depends on the graph representation.
Why it matters: These bounds help you compare implementations and understand their scaling costs. - Local processing with excess flow: Explain how Push–Relabel replaces global path traversal with neighbor-based operations and why intermediate nodes may temporarily hold excess flow.
Why it matters: This is the central design distinction behind the algorithm’s local operations. - Height growth and termination: Explain how increasing, bounded heights limit relabeling and prevent an infinite processing loop.
Why it matters: The height limit explains why local relabel operations cannot continue forever. - Residual minimum cut: Describe how the section identifies the source side of a minimum cut when the algorithm terminates.
Why it matters: It connects the completed flow calculation to the network bottleneck it reveals. - Active node processing order: Explain why the order of active-node processing matters and name the two queue choices given to reduce redundant cycles.
Why it matters: It explains why active-node scheduling is a performance choice, not just an implementation detail.
Key terms: time complexity, highest-label selection heuristic, space complexity, adjacency lists, local node relaxation, residual graph, excess flow, global conservation constraints, heights, relabel operations
10.4 Summary
10.5 References
This section lists external references for Push–Relabel implementations, explanations, applications, and library documentation.
Where this is used later
- (chapter intro) (chapter 11) · The earlier maximum-flow problem provides the contrast used in this introduction.
Concepts explained in this chapter
- push-relabel algorithmThe push-relabel algorithm computes a maximum flow by maintaining a preflow and vertex height labels, then locally pushing excess flow and relabeling vertices.
- maximum flowThe problem of finding the greatest feasible flow from a source to a sink in a capacitated network.
- excess flowExcess flow is the net amount of incoming flow currently retained at a vertex rather than sent onward.
- relabel operationA relabel operation raises an active vertex's height to enable a valid push along an edge with residual capacity.
- preflowA preflow is a flow assignment that respects edge capacities and flow conservation at intermediate vertices may be temporarily violated by allowing excess flow.
- active nodeAn active vertex is a vertex with positive excess flow that can undergo a push or relabel operation.
- push operationA flow push sends excess flow to a neighboring vertex with residual capacity whose height is exactly one unit lower.
- residual capacityResidual capacity is the additional flow that can be sent along an edge, accounting for its capacity and current flow.
- height functionA height function assigns labels to network vertices to determine which flow operations are admissible in the push-relabel algorithm.
- flow conservationFlow conservation is the requirement that, at each intermediate vertex, the total incoming flow equals the total outgoing flow.
- space complexityA measure of how an algorithm's memory usage grows as a function of input size.
- time complexityA measure of how an algorithm's running time grows with input size.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
