Introduction

Network flow problems lie at the heart of countless optimization tasks across logistics, telecommunications, transportation, and data science. The fundamental challenge is to route as much flow as possible from a source node to a sink node while respecting capacity limits on every edge. For small or medium networks, classic methods like the Ford-Fulkerson algorithm often suffice. However, as networks grow to millions of nodes and edges—common in modern big data and cloud infrastructure—traditional approaches become prohibitively slow. The push-relabel algorithm offers a powerful, scalable alternative that excels in large-scale settings. By maintaining a preflow and performing local push and relabel operations, it converges to the optimal flow far more efficiently than many earlier techniques. This article provides an authoritative, production-ready explanation of the push-relabel algorithm, its inner workings, practical implementation tips, and its outstanding performance on massive network flow problems.

Understanding Network Flow Problems

A network flow problem is defined on a directed graph G = (V, E) with a source s, a sink t, and a capacity function c(u, v) ≥ 0 for each edge. The goal is to find the maximum feasible flow from s to t such that for every node (except source and sink), the total incoming flow equals the total outgoing flow—this is known as flow conservation. Edges cannot carry more than their capacity. This classic problem, the maximum flow problem, appears in diverse applications: allocating bandwidth in computer networks, scheduling jobs on machines, matching supply and demand in supply chains, and even image segmentation in computer vision.

Real-world instances often involve tens of thousands to millions of vertices. For example, a telecommunications backbone may have thousands of routers and millions of connections; a logistics company’s distribution network can have similar complexity. In such cases, an algorithm that scales quadratically or even linearly with the number of vertices and edges becomes essential. The push-relabel algorithm fits this need by operating in a highly localized manner, which also lends itself to parallel and distributed implementations.

Limitations of Traditional Maximum Flow Algorithms

Algorithms like Ford-Fulkerson use augmenting paths to increment flow until no more can be found. Their worst-case complexity depends on the maximum flow value F – O(F·E) – which can be enormous when capacities are large. Edmonds-Karp improves this to O(V·E²) by always using shortest augmenting paths in terms of number of edges, but this is still too slow for graphs with hundreds of thousands of edges. Moreover, traditional algorithms require scanning the entire residual graph to find augmenting paths, leading to poor cache locality and limited parallelism.

In contrast, the push-relabel algorithm avoids the global search for augmenting paths. Instead, it floods the network with a preflow (excess flow that may violate conservation temporarily) and then gradually corrects the excesses by pushing flow downstream toward the sink. The algorithm’s local operations—push and relabel—can be executed in any order, making it highly adaptable to modern hardware and large graphs.

The Push-Relabel Algorithm Explained

The push-relabel algorithm, introduced by Goldberg and Tarjan in 1988, works with a preflow. A preflow satisfies capacity constraints but allows nodes (other than source and sink) to have a net inflow, called excess. Each node is assigned a height (also called distance label). The source is initially at height V (number of vertices) and the sink at height 0. All other nodes start at height 0. The algorithm pushes flow from higher to lower nodes, and when a node with excess has no neighbor of lower height, it relabels (increases its height) to enable further pushes. The process continues until no node (except source and sink) has positive excess.

Key Concepts

  • Preflow: A function f on edges satisfying 0 ≤ f(u,v) ≤ c(u,v) and for every node v ≠ s,t, the net flow into v (total incoming minus outgoing) is non‑negative. This net inflow is called the excess at v: e(v) = Σ f(u,v) – Σ f(v,u).
  • Height: An integer label h(v) representing a lower bound on the distance to the sink in the residual graph. The source has fixed height n, sink height 0. The algorithm maintains the invariant h(v) ≤ h(u) + 1 for every edge (u,v) in the residual graph.
  • Admissible Edge: An edge (u,v) in the residual graph with h(u) = h(v) + 1. Flow can only be pushed along admissible edges.

Core Operations: Push and Relabel

  1. Push(u, v): When node u has excess e(u) > 0 and there exists an admissible edge (u,v), push as much flow as possible – min(e(u), residual capacity cf(u,v)) – from u to v. The excess of v increases accordingly; the excess of u decreases.
  2. Relabel(u): When node u has excess but no admissible edge, increase h(u) to the smallest value such that at least one edge (u,v) becomes admissible. Concretely: h(u) = 1 + min{ h(v) | (u,v) in residual graph }.

The algorithm repeatedly selects an active node (a node with positive excess, excluding source and sink) and performs either a push or a relabel. The most common selection strategy is the Highest Label First (HLF) heuristic, which picks the active node with the highest height. This bounds the number of pushes and relabels and often gives the best performance in practice.

Algorithm Steps (Simplified)

  1. Initialization: Set h(s) = |V|, h(t) = 0, and all other heights to 0. Set preflow by saturating all outgoing edges from source: push flow = c(s,v) for each neighbor v. This gives those neighbors excess. Set all other edges to zero flow.
  2. Loop: While there exists an active node (excess > 0) other than s and t:
    • Select an active node u (e.g., highest label).
    • For each outgoing edge (u,v) in the residual graph, if admissible, push as much as possible.
    • If after checking all edges no push was possible, relabel u.
  3. Termination: When no active nodes remain, the preflow is a valid maximum flow.

At termination, the heights satisfy the invariant and no excess exists; the flow on edges respects capacities and conservation, yielding the maximum flow value equal to the net outflow from the source.

Advantages for Large-Scale Problems

The push-relabel algorithm excels where other algorithms stumble. Its worst‑case time complexity is O(V²E), but with the highest‑label selection rule it becomes O(V²√E). Moreover, the algorithm processes each node locally using only adjacency information, so it is cache‑friendly and highly parallelizable. In practice, it often runs in near‑linear time on many real‑world graphs, making it the method of choice for large‑scale network flow software (e.g., Boost Graph Library, Google OR‑Tools, and many custom implementations).

Another key advantage is its adaptability to high capacities. Because push‑relabel does not depend on the magnitude of capacities—only on the number of vertices and edges—it handles networks with capacities in the billions as easily as small ones. This is particularly important in applications like bandwidth reservation and monetary flow analysis.

Furthermore, push‑relabel can be extended to dynamic graphs where capacities change over time. Local updates (adding an edge or changing capacity) can be handled by re‑running a small subset of operations rather than solving from scratch. This makes it useful for live traffic engineering and adaptive resource allocation.

Heuristics and Optimizations

To achieve top performance, two critical enhancements are commonly applied:

  • Global Relabeling: Periodically recompute exact distances (heights) from all nodes to the sink using a reverse breadth‑first search. This resets heights to accurate lower bounds, drastically reducing the number of relabel operations. Global relabeling is typically performed after every O(V) pushes or whenever the algorithm seems stuck.
  • Gap Heuristic: If at any point there is a “gap” in the height range—i.e., no node at a certain height k—then all nodes with height greater than k can be immediately relabeled to V (or infinity), effectively cutting off flow that can never reach the sink. This prevents useless pushes and speeds convergence.

Other common optimizations include using a FIFO queue for active nodes (simpler but still effective) and discharge rules that combine multiple pushes before relabeling. In practice, the highest‑label selection combined with global relabeling and gap heuristics yields the fastest known serial implementation for general networks.

Implementation Tips

When implementing the push‑relabel algorithm for production use, consider the following:

  • Data structures: Represent the graph with adjacency lists storing edges and reverse edges (like paired arcs). Each edge holds capacity, flow, and pointer to the reverse edge. Keep arrays for height, excess, and a list (or priority queue) of active nodes.
  • Active node selection: For the highest‑label strategy, maintain a bucket array (ranging from 0 to V) to store nodes by their height. This gives O(1) insertion and removal and allows immediate access to the next active node with highest label.
  • Global relabeling: Implement a reverse BFS from the sink, computing the exact shortest path distance in the residual graph. Set heights accordingly. This step can be executed every O(V) pushes or after every 1–2 seconds of wall‑clock time in a real‑time system.
  • Memory efficiency: Store capacities as integers or floats as needed. For extremely large graphs (millions of nodes), use compressed sparse row formats and careful cache alignment. Avoid recursion; use iterative loops.
  • Parallelization: Push‑relabel is naturally parallel because active nodes can process simultaneously if they are far enough apart. Common approaches use graph partitioning (e.g., via METIS) and synchronize after each global relabel.

For those seeking a ready‑to‑use implementation, the Boost Graph Library provides an efficient push‑relabel solver (see Boost push_relabel_max_flow). Similarly, Google’s OR‑Tools includes a maximum flow solver that uses a variant of push‑relabel (see OR‑Tools MaxFlow). For academic reference, the original paper by Goldberg and Tarjan is still a cornerstone (A new approach to the maximum flow problem).

Real-World Applications

The push‑relabel algorithm is not a theoretical curiosity—it is deployed daily in systems that require maximum flow computations at scale:

  • Transportation and logistics: Optimizing freight routing through hub‑and‑spoke networks with capacity‑constrained trucks, trains, or cargo ships. The algorithm handles tens of thousands of nodes representing distribution centers.
  • Telecommunications: Calculating maximum data throughput in fiber‑optic or wireless mesh networks. As networks evolve, dynamic capacity changes are handled efficiently with push‑relabel.
  • Image segmentation: In computer vision, the max‑flow/min‑cut formulation is used for interactive segmentation. The push‑relabel algorithm (specifically the Boykov‑Kolmogorov variant) underpins many state‑of‑the‑art tools like the GraphCut algorithm.
  • Airline crew scheduling: Matching pilots to flights while respecting union rules and flight hours can be modeled as a bipartite matching, solvable by max‑flow. Major airlines use push‑relabel to generate schedules nightly.
  • Cloud resource allocation: Virtual machine assignment in data centers, where bandwidth caps and server capacities form a network flow problem. Push‑relabel’s speed allows near‑real‑time adaptation.

Conclusion

The push‑relabel algorithm stands as one of the most efficient and scalable methods for solving large‑scale network flow problems. Its use of preflow and local operations avoids the global scanning overhead of traditional augmenting path algorithms, making it suitable for graphs with millions of nodes and edges. With key optimizations like global relabeling and the gap heuristic, push‑relabel achieves excellent practical performance. Engineers and researchers deploying network flow in real‑world systems—from telecommunications to image processing—rely on its proven speed and adaptability. Whether you are implementing it from scratch or using a library, understanding the algorithm’s internals ensures you can tune it for your specific large‑scale challenges. For further study, the Wikipedia entry on push‑relabel provides a solid overview, and the original literature remains an essential reference.