Push-Relabel Algorithm
Also known as: preflow-push algorithm, Goldberg-Tarjan algorithm
The Push-Relabel Algorithm, developed by Andrew V. Goldberg and Robert E. Tarjan in 1988, is a highly efficient method for computing maximum flow in networks. Unlike augmenting path methods, it maintains a preflow and uses local push and global relabeling operations to drive flow toward the sink, achieving superior worst-case complexity.
Key highlights
- Superior worst-case time complexity: O(V³) or O(V²√E) with gap heuristic
- Highly efficient in practice, especially for large and dense networks
- Locality of operations (push/relabel) allows for good cache performance
- Amenable to parallelization and distributed implementations
- Multiple implementation variants for different problem structures
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Apply the push-relabel algorithm for computing maximum flow in large dense networks where augmenting path methods become inefficient. It is particularly effective for networks with thousands or millions of edges. Use it when you need guaranteed polynomial-time performance and want to leverage modern data structures. For sparse networks or educational purposes, augmenting path methods may be simpler to understand and implement.
Strengths & limitations
- Superior worst-case time complexity: O(V³) or O(V²√E) with gap heuristic
- Highly efficient in practice, especially for large and dense networks
- Locality of operations (push/relabel) allows for good cache performance
- Amenable to parallelization and distributed implementations
- Multiple implementation variants for different problem structures
- More complex to understand and implement than augmenting path methods
- Requires careful handling of data structures (discharge lists, gap heuristics) for optimal performance
- Worst-case complexity still higher than some specialized algorithms for special graph classes
- Less intuitive understanding of the solution process compared to augmenting paths
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
What is the difference between preflow and flow?
Preflow temporarily allows nodes to hold excess flow (flow in minus flow out can be positive), whereas true flow must be conserved at all nodes except source and sink. The algorithm terminates when preflow becomes a valid flow.
What is the purpose of the height function?
Heights create a quasi-distance measure: flow can only be pushed downhill (from higher to lower heights), preventing unnecessary cycles and ensuring termination. Heights are increased through relabeling to create new paths when needed.
What is the gap heuristic and why is it important?
The gap heuristic detects when no node has a height in a certain range, indicating that some nodes cannot reach the sink. These nodes and their excess are quickly identified and processed, significantly improving practical performance.
How does push-relabel compare in practice to Edmonds-Karp?
Push-relabel has better worst-case complexity and typically outperforms Edmonds-Karp on large networks, but for small networks or sparse graphs, Edmonds-Karp may be simpler to implement with competitive performance.
Sources
- 1.Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
- 2.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Push-Relabel Algorithm. ScholarGate. https://scholargate.app/operations-research/push-relabel-algorithm