Skip to content
Back to search results

Push-Relabel Algorithm

Introduced by
Andrew V. Goldberg and Robert E. Tarjan
Year
1988
Type
algorithm
Family
Graph Algorithms
Font size

What does it do?

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.

The intuition behind the method

The algorithm maintains a 'height' or 'distance label' for each node and uses preflow (where nodes can temporarily exceed sink demand). It repeatedly pushes excess flow from higher-labeled nodes to lower-labeled neighbors and relabels nodes to create paths to the sink. The key insight is that by maintaining height invariants and using efficient data structures, the algorithm avoids exploring the entire graph repeatedly, as augmenting path methods must do. The algorithm terminates when all excess flow reaches the sink.

History

Goldberg and Tarjan published their push-relabel algorithm in 1988, introducing a fundamentally different paradigm for maximum flow computation. Their algorithm achieved O(V³) worst-case complexity, an improvement over the O(VE²) of Edmonds-Karp. Over subsequent decades, numerous variants have been developed, including gap heuristics (Goldberg and Tarjan, 1990), highest-label rules, and the latest variants achieving near-linear empirical performance on real-world networks.

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.

Limitations and considerations

  • 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

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • 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

Applications

  • Network routing: computing maximum throughput in large-scale communication networks
  • Image processing: using max-flow for image segmentation and matting applications
  • Airline optimization: determining maximum passenger flow through complex routing networks
  • Power grid analysis: computing maximum power transmission capacity in electrical networks
  • Supply chain management: optimizing product flow through multi-tier distribution networks
  • Biological networks: analyzing maximum flow in metabolic and protein interaction networks

How it works

How it works

1

Set the height of the source to the number of vertices, all other heights to zero. Saturate all edges leaving the source, creating initial preflow (excess at neighboring nodes).

2

Repeatedly select an active node (with excess flow) and either push excess to a lower-height neighbor or relabel the node to increase its height. Use efficient selection strategies and discharge operations to minimize iterations.

3

Continue until no active nodes remain, at which point all preflow has been resolved into a maximum flow from source to sink.

Common pitfalls

  • Incorrectly implementing height updates or push operations leading to non-maximum flows
  • Neglecting to use gap heuristics and efficient node selection, resulting in poor practical performance
  • Failing to properly maintain the preflow invariant (excess at nodes and capacity constraints on edges)

Frequently asked questions

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.

Related methods

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.

    Open DOI reference
    Copied.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    Open publication reference
    Copied.