How to Learn Push–Relabel Maximum Flow: Preflows, Excess, Height Labels, Discharge and Global Relabeling

Wait, What?

Maximum flow can be solved without repeatedly searching for a complete source-to-sink augmenting path.

Push–relabel changes the viewpoint. Instead of asking, “Can I find another whole path from source to sink?”, it allows intermediate vertices to temporarily hold excess flow. The algorithm then pushes that excess locally along admissible residual edges and raises vertex labels when necessary until no active intermediate vertex remains.

This makes push–relabel one of the best algorithms for learning how a global optimum can emerge from local operations governed by a strong invariant.

Quick Answer

Learn push–relabel in this order: residual network → preflow → excess → height labels → admissible edge → push → relabel → discharge → active-vertex policy → global relabeling/gap heuristics → correctness and implementation. Do not start with the optimized code. First trace a tiny network and explain why flow is allowed to accumulate at intermediate vertices.

1. Begin With the Maximum-Flow Contract

A directed flow network has a source s, a sink t and capacities on edges. A valid final flow must respect capacity limits and conserve flow at every intermediate vertex. The goal is to maximize the amount sent from s to t.

Ford–Fulkerson-style methods maintain a valid flow throughout and repeatedly augment along source-to-sink paths. Push–relabel deliberately relaxes one condition during the computation: intermediate vertices may temporarily receive more flow than they send onward.

2. Preflow Is Flow With Temporary Excess

For a vertex v other than s and t, define its excess:

excess(v) = inflow(v) - outflow(v)

A preflow permits excess(v) ≥ 0. That extra flow is not lost; it is waiting at v to be pushed elsewhere or eventually returned toward the source.

This is the conceptual leap. The algorithm optimizes first, restores exact flow conservation by the end, and uses residual edges to move excess around safely.

3. Residual Capacity Still Governs Every Move

For each directed edge (u,v), the residual network records how much additional flow may be pushed forward and how much already-sent flow may be cancelled through a reverse edge. A push is legal only when residual capacity is positive.

The reverse residual edge is essential. Without it, an early local decision could never be corrected.

4. Height Labels Replace Explicit Path Search

Each vertex gets a nonnegative integer height label h(v). The source begins high, typically h(s)=|V|, while other vertices begin at zero. The labels obey a validity condition on residual edges:

if residual_capacity(u,v) > 0:
    h(u) ≤ h(v) + 1

An edge is admissible for pushing when it has positive residual capacity and:

h(u) = h(v) + 1

So excess is pushed “downhill” by exactly one label step.

5. Initialization Saturates the Source Edges

Set h(s)=|V| and h(v)=0 for every other vertex. Then saturate every outgoing edge from s. Neighbours of the source may suddenly have positive excess, becoming active vertices.

This aggressive initialization is intentional. Rather than cautiously discovering one augmenting path, push–relabel creates work everywhere near the source and then resolves it locally.

6. The Push Operation

If u is active and (u,v) is admissible, push:

delta = min(excess(u), residual_capacity(u,v))

Then update forward and reverse residual capacities, reduce excess(u), and increase excess(v). The push may be saturating if it fills the residual edge or nonsaturating if u runs out of excess first.

7. The Relabel Operation

If u is active but has no admissible outgoing residual edge, raise its height just enough to create one:

h(u) = 1 + min(h(v))
       over residual edges (u,v) with positive capacity

Relabeling never moves flow. It changes which local directions are considered downhill.

8. Discharge Means Keep Working on One Active Vertex

A common implementation defines a discharge operation: repeatedly push from an active vertex along admissible edges; when no admissible edge remains, relabel it; continue until its excess becomes zero or the chosen scheduling policy stops processing it.

discharge(u):
    while excess(u) > 0:
        if current residual edge is admissible:
            push(u,v)
        elif more edges remain:
            advance current edge
        else:
            relabel(u)
            reset current edge

The “current edge” pointer is not a cosmetic optimization. It prevents rescanning the same failed adjacency entries over and over.

9. Work a Four-Vertex Example

Suppose s connects to a and b, and both can send flow toward t. Initialization saturates s→a and s→b, so a and b hold excess. If a has an admissible residual edge to t, it pushes directly. If b cannot push to t because its outgoing capacity is full or its label relation is wrong, b may relabel and later push either toward t or back through residual structure.

The key observation is that excess can move independently in different parts of the graph. There is no requirement that the algorithm know a complete augmenting route in advance.

10. Why the Algorithm Eventually Produces a Real Flow

At termination, no intermediate vertex is active. Therefore every intermediate vertex has zero excess, restoring flow conservation. Capacity constraints have been maintained throughout by residual-capacity checks. The remaining proof shows that the valid height labeling certifies there can be no residual s-to-t augmenting path, so the resulting flow is maximum.

This is a useful proof pattern: termination plus maintained invariants imply both feasibility and optimality.

11. Active-Vertex Order Matters for Performance

The generic method allows freedom in choosing which active vertex to process. FIFO queues, highest-label selection and other policies can behave very differently in practice and in analysis.

Current NetworkX documentation uses a highest-label preflow-push implementation. Boost.Graph also provides push–relabel maximum flow. This is a reminder that “push–relabel” names a family of implementations, not one immutable line-by-line program.

12. Global Relabeling Repairs Stale Distance Information

Height labels act like lower-bound distance information in the residual network, but local relabels may leave many labels far from the true current distance to the sink. A global relabel heuristic periodically runs a reverse breadth-first search from t over the residual graph and resets labels to accurate residual distances.

This extra O(V+E) work can substantially reduce wasted local pushes. It is a classic example of spending occasional global work to make many later local decisions better.

13. The Gap Heuristic

If no vertex has a particular height k, then vertices above that gap but below the source’s special height cannot reach the sink through admissible residual progress under the current structure. Implementations can raise such vertices aggressively, effectively recognizing that their excess must eventually return toward the source.

The heuristic is powerful but should be added only after the core invariant is correct.

14. Complexity Depends on the Variant

Goldberg and Tarjan’s foundational analysis gave polynomial guarantees for generic and refined implementations. Boost.Graph documents O(V³) for its push–relabel routine, while current NetworkX documentation states O(n²√m) for its highest-label preflow-push implementation. These are not contradictions: they describe different implementation choices and analyses.

Professional algorithm reading always asks: which variant, under which data structure and scheduling policy, is this bound describing?

15. Data Structures Matter

• Store explicit reverse-edge references so residual updates are O(1).
• Keep excess and height arrays contiguous when possible.
• Use a current-edge index during discharge.
• Maintain active-vertex buckets efficiently for highest-label selection.
• Track counts of vertices at each height if using the gap heuristic.
• Be careful with numeric capacity types and overflow.

16. Common Failure States

• Forgetting that a preflow may violate ordinary conservation temporarily.
• Pushing on an edge with no positive residual capacity.
• Using h(u) > h(v) instead of the exact admissibility condition h(u)=h(v)+1 in the standard formulation.
• Relabeling without taking the minimum reachable neighbour height.
• Failing to update the reverse residual edge.
• Treating the source or sink like ordinary active vertices.
• Adding heuristics before testing the basic push/relabel invariant.
• Quoting one complexity bound as though every push–relabel implementation has it.

17. Practice Ladder: Beginner to Professional

• Beginner: compute residual capacities and vertex excess after source-edge saturation.
• Foundation: trace pushes and relabels on a five-vertex network, writing h and excess beside each vertex after every step.
• Intermediate: implement FIFO discharge with current-edge pointers and compare the result to a trusted max-flow implementation.
• Advanced: add highest-label selection, global relabeling and the gap heuristic one at a time, measuring operation counts.
• Professional: benchmark against Dinic and other max-flow implementations on sparse, dense, unit-capacity and adversarial graph families while recording throughput and tail latency.
• Proof transfer: explain why no active intermediate vertices plus a valid residual labeling is enough to certify a maximum flow.

18. A Better Way to Study the Algorithm

The most effective learning sequence is not “read pseudocode and copy it.” Use a worked example with explicit subgoals: maintain residual capacity → locate active excess → choose admissible local move → relabel only when blocked → restore conservation by termination → verify max-flow value. Computing-education research on subgoal-labelled worked examples, code tracing and algorithm visualisation supports this progression from concrete state changes to abstract invariants.

Learning Hall Boundary

This article owns push–relabel as a specific maximum-flow method. It complements, but does not replace, the existing network-flow foundations and the separate Dinic draft. It also does not take over general graph traversal, amortized-analysis, parallel-computing or MindOS learning-process jobs.

Evidence Boundary

Andrew Goldberg and Robert Tarjan introduced the preflow-based approach in A New Approach to the Maximum-Flow Problem, Journal of the ACM 35(4), 1988, DOI 10.1145/48014.61051; Princeton hosts the original technical-report record: Princeton — A New Approach to the Maximum Flow Problem. Current implementation references include Boost.Graph push–relabel documentation and NetworkX preflow_push documentation. The teaching structure also reflects computing-education evidence for worked examples, subgoal labelling and active tracing.

Professional rule: you understand push–relabel when you can explain why temporary excess is safe, state the height invariant, trace a discharge without guessing, and distinguish the generic algorithm from the scheduling and heuristic choices that make real implementations fast.