12.6 Push-Relabel Algorithm
The algorithms developed so far share a common strategy.
12.6 Push-Relabel Algorithm
Problem
The algorithms developed so far share a common strategy. They search for augmenting paths from the source to the sink and then push additional flow along those paths.
This approach works well, but it has an important limitation. Every augmentation requires discovering a complete path through the residual network before any progress can be made.
In large networks, repeatedly searching for source-to-sink paths can become expensive. More importantly, the existence of a useful path may depend on flow adjustments occurring far away in the graph.
Is it possible to compute a maximum flow without searching for augmenting paths at all?
The push-relabel algorithm answers this question with a completely different perspective. Instead of moving flow along complete paths, it moves flow locally between neighboring vertices and gradually transforms an infeasible flow into a maximum flow.
Solution
Push-relabel maintains a preflow rather than a valid flow.
A preflow satisfies capacity constraints but does not require flow conservation at intermediate vertices. A vertex may temporarily contain more incoming flow than outgoing flow.
This surplus is called excess flow.
The algorithm repeatedly moves excess flow toward the sink while using vertex heights to guide the movement.
The process consists of two operations:
- Push
- Relabel
Together, these operations eventually eliminate all excess flow and produce a maximum flow.
Understanding Preflows
Recall that ordinary flow requires:
incoming(v) = outgoing(v)
for every internal vertex.
Push-relabel relaxes this condition.
Instead, it permits:
incoming(v) ≥ outgoing(v)
The difference is stored as excess.
For example:
| Edge | Flow |
|---|---|
| S → A | 10 |
| A → B | 4 |
Vertex A receives:
10
units and sends:
4
units.
Its excess becomes:
10 - 4 = 6
The algorithm must eventually remove this excess.
Height Labels
Each vertex receives a nonnegative integer called its height.
The height acts as a potential function that guides flow movement.
Flow may move only from a higher vertex to a lower vertex.
Think of the heights as elevations in a landscape.
Water naturally flows downhill.
If a vertex cannot send flow to any lower neighbor, its height increases until a downhill path becomes available.
Initial State
The algorithm begins by saturating all edges leaving the source.
Consider:
S → A = 10
S → B = 8
Initially:
| Edge | Flow |
|---|---|
| S → A | 10 |
| S → B | 8 |
The source pushes as much flow as possible immediately.
This creates excess at A and B.
Initial heights:
| Vertex | Height |
|---|---|
| S | V |
| Others | 0 |
where:
V = number of vertices
Giving the source the largest height ensures flow can move away from it.
Push Operation
Suppose:
height(A) = 3
height(B) = 2
and residual capacity exists on:
A → B
Flow may be pushed because:
3 = 2 + 1
The push amount equals:
min(
excess(A),
residual(A,B)
)
Example:
| Quantity | Value |
|---|---|
| Excess at A | 7 |
| Residual capacity | 4 |
Push:
4
units.
New excess:
| Vertex | Excess |
|---|---|
| A | 3 |
| B | +4 |
The excess moves closer to the sink.
Relabel Operation
Suppose vertex A has excess but cannot push flow.
Example:
height(A) = 2
height(B) = 2
height(C) = 2
Pushing requires:
height(A)
=
height(neighbor) + 1
No such neighbor exists.
The algorithm increases A's height.
New height:
1 + minimum neighboring height
Therefore:
height(A) = 3
Now pushing becomes possible.
Relabeling creates a new downhill direction.
Example
Consider:
S → A (10)
A → T (5)
Initialization
Saturate source edge:
| Edge | Flow |
|---|---|
| S → A | 10 |
Excess:
| Vertex | Excess |
|---|---|
| A | 10 |
Heights:
| Vertex | Height |
|---|---|
| S | 3 |
| A | 0 |
| T | 0 |
Relabel
A cannot push to T because:
0 ≠ 0 + 1
Increase height:
height(A) = 1
Push
Now:
1 = 0 + 1
Push:
5
units to T.
Remaining excess:
5
at A.
Relabel Again
Residual graph now contains reverse edge:
A → S
Height of S is:
3
Relabel A:
height(A) = 4
Push Back
Excess returns to S through the residual edge.
The algorithm eventually reaches a stable state.
Maximum flow:
5
Active Vertices
A vertex is active when:
excess(v) > 0
and:
v ≠ source
v ≠ sink
Push-relabel repeatedly selects active vertices and processes them until no active vertices remain.
When the algorithm terminates, every internal vertex satisfies flow conservation.
The resulting preflow becomes a valid maximum flow.
Generic Algorithm
Initialize:
- Set source height to V.
- Saturate source edges.
- Create excess at neighboring vertices.
Repeat:
- Select active vertex.
- If push possible, push flow.
- Otherwise relabel.
- Continue until no active vertices remain.
Return resulting flow.
Pseudocode
initialize preflow
while active vertex exists:
if push possible:
push
else:
relabel
The actual implementation contains additional optimizations, but the central idea remains remarkably simple.
Why It Works
Push operations move excess toward lower heights.
Relabel operations create new opportunities for movement.
Heights never decrease.
Eventually:
- excess cannot circulate forever
- heights remain bounded
- all excess reaches the sink or returns to the source
At termination:
no active vertices
and the preflow becomes a feasible maximum flow.
Complexity Analysis
The original push-relabel algorithm runs in:
O(V²E)
time.
This is comparable to Dinic's algorithm in worst-case analysis.
However, practical performance is often excellent.
With additional heuristics, push-relabel frequently outperforms augmenting-path algorithms on dense networks.
Important Optimizations
Highest-Label Selection
Always process the active vertex with maximum height.
This tends to move excess aggressively toward completion.
Gap Heuristic
If a height level becomes empty, many vertices can be relabeled immediately.
This significantly reduces work.
Global Relabeling
Periodically recompute exact distances from the sink.
The resulting heights better reflect the structure of the residual graph.
This optimization often produces substantial speedups.
Comparison with Dinic
| Feature | Dinic | Push-Relabel |
|---|---|---|
| Main idea | Augmenting paths | Local excess movement |
| BFS phases | Yes | Optional |
| DFS blocking flow | Yes | No |
| Preflow | No | Yes |
| Dense graph performance | Good | Excellent |
| Implementation complexity | Moderate | Moderate |
Both algorithms remain widely used in practice.
Applications
Push-relabel is especially effective in:
- Dense flow networks
- Computer vision
- Image segmentation
- Network optimization
- Resource allocation
- Large industrial planning systems
Many state-of-the-art maximum-flow solvers are based on push-relabel variants rather than augmenting-path algorithms.
Common Mistakes
Violating Height Rules
Flow may only move along admissible edges:
height(u)
=
height(v) + 1
Ignoring this condition breaks correctness.
Forgetting Excess Updates
Every push must update excess values at both endpoints.
Relabeling Incorrectly
The new height must be:
1 + minimum neighbor height
among residual neighbors.
Processing Inactive Vertices
Vertices with zero excess require no work.
Processing them wastes time.
Discussion
Push-relabel represents a major conceptual shift in network flow theory. Earlier algorithms view flow as something that travels from source to sink along complete paths. Push-relabel instead treats flow as a local quantity that accumulates, moves, and redistributes throughout the graph.
This perspective leads to algorithms that often scale extremely well in practice. Many modern maximum-flow implementations use push-relabel as their primary engine, particularly when working with dense graphs or large optimization problems.
Takeaway
Push-relabel abandons augmenting paths and operates directly on excess flow. By maintaining a preflow and using height labels to guide local movement, it transforms maximum-flow computation into a sequence of push and relabel operations.
The next recipe examines the minimum cut problem and develops the fundamental duality that underlies the entire theory of network flow: the max-flow min-cut theorem.