Push-Relabel Maximum Flow

Imagine a water distribution network: pipes connect junctions, each pipe has a maximum capacity, and you want to move as much water as possible from a source to a sink. This is the maximum flow problem — one of the most fundamental in all of combinatorial optimization.

The classic approach, Ford-Fulkerson (1956), finds a path from source to sink with leftover capacity and pushes flow along it, repeating until no such path exists. It works, but on dense graphs with many edges the repeated global path searches are expensive.

In 1988 Andrew Goldberg and Robert Tarjan introduced push-relabel, a fundamentally different strategy. Instead of looking for end-to-end paths, the algorithm:

1. Preflows the source — it immediately saturates all outgoing edges of the source, creating "excess" flow at neighbors.
2. Assigns every node a height label (a non-negative integer). Flow may only be pushed downhill (from a node to a neighbor with a strictly lower label).
3. Repeatedly pushes excess from an active node (one with excess > 0) to a lower neighbor, or relabels the node (raises its height) when no downhill neighbor exists.
4. Terminates when no active nodes remain — any excess that could not reach the sink flows back to the source, and the net flow into the sink equals the maximum flow.

The result is an algorithm that achieves $O(V^{2}E)$ time in general, and $O(V^{3})$ with the FIFO selection rule — both better than Ford-Fulkerson's $O(VE^{2})$ on dense graphs.

Compare it with the path-by-path approach in our max-flow article: push-relabel trades global path searches for local, node-by-node operations, and wins on graphs where E is large relative to V.

The demo below shows a six-node flow network (S → A, B → C, D → T) with capacities on each edge. Click Step to advance the algorithm one operation at a time, or Run to animate it to completion. The height of each node is shown inside its circle; orange nodes carry excess flow.

<p class="hint">{{hint}}</p>
<div class="canvas-wrap"><canvas id="c" width="520" height="300"></canvas></div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas-wrap { overflow-x: auto; }
canvas { display: block; border-radius: 10px; background: #f4f7fa; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.done { color: #1d3557; }
.status.active { color: #b86a00; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

// Code not found

Watch how excess accumulates near the source before gradually flowing — or being pushed back — through the network. Each relabel raises a node's height when it has no downhill neighbor to receive its excess. The algorithm terminates when only S and T carry non-zero flow balance.

Push-relabel's performance is proven (not conjectured) and rests on tight bounds for the two operations:

• Relabels: each node can be relabeled at most 2V − 1 times before its height exceeds 2V (the upper bound that prevents infinite loops). Total relabels ≤ $2V^{2}$.
• Saturating pushes: a push from u to v is saturating when it empties the edge capacity. Before u can push to v again, v must be relabeled above u, then u above v — at least 2 relabels per edge direction. Total saturating pushes ≤ 2VE.
• Non-saturating pushes: the tricky part. Each non-saturating push moves excess to a lower node; a potential-function argument shows at most $O(V^{2}E)$ such pushes total.
• Combined: $O(V^{2}E)$ overall.

With the FIFO selection rule (always process the oldest active node in a queue), the non-saturating push bound drops to $O(V^{3})$ — independent of E, which makes it ideal for very dense graphs (E ≈ $V^{2}$).

Comparison with classical algorithms:

Status: solved. Maximum flow is in P. The push-relabel algorithm is a practical workhorse used in production implementations of maximum-flow solvers, and its $O(V^{3})$ bound was proved by Goldberg & Tarjan in their landmark 1988 paper.

Maximum flow is one of the most-reduced-to problems in combinatorial optimization. Push-relabel, being faster on dense graphs, is the implementation of choice in many real settings:

• Image segmentation: cutting an image into foreground/background is a minimum-cut problem (equivalent to max-flow by the max-flow min-cut theorem). Dense pixel grids make push-relabel the standard choice here.
• Bipartite matching: finding the maximum matching in a bipartite graph reduces to max-flow in a network with V + E nodes and edges.
• Project selection and closure problems: which projects to fund (given dependencies and profits) is a max-flow / min-cut problem on a DAG.
• Network routing: routing bandwidth in telecommunications and data-center networks uses max-flow to saturate links.
• Scheduling and resource allocation: assigning tasks to machines respecting capacity constraints reduces to flow problems that push-relabel solves efficiently.

Whenever you encounter a "capacity-constrained routing" or "binary label assignment" problem, max-flow — and likely push-relabel — is lurking underneath. Understanding push-relabel means you can reduce to it and get a provably optimal solution in polynomial time.

Push-relabel stands as a lesson in algorithmic thinking: the obvious strategy (find a path, push flow along it) is not always the fastest. By abandoning global path searches in favor of purely local operations — push excess downhill, raise height when stuck — Goldberg and Tarjan achieved a provably better bound for dense networks.

The $O(V^{3})$ FIFO variant in particular is a reminder that the right data structure and selection rule can improve a complexity class without changing the underlying algorithm idea. And behind every image-segmentation pipeline, every scheduling optimizer, and every network router that finds the true optimum lies the same elegant insight: saturate locally, correct globally, and the max-flow emerges.

Maximum flow is in P — it is one of the algorithmic success stories. But linear programming duality shows that even "easy" problems can have surprisingly rich structure. Push-relabel is where that structure becomes beautifully concrete.