Push–relabel maximum flow algorithm
Efficient maximum flow algorithm using push and relabel operations.
The push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. It maintains a preflow and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. It is considered one of the most efficient maximum flow algorithms.
- field
- Mathematical optimization
- known_for
- Maximum flow algorithm with strongly polynomial O(V²E) time complexity
Lore & Background
The push–relabel algorithm was designed by Andrew V. Goldberg and Robert Tarjan. Both papers detail a generic form of the algorithm terminating in O(V²E) along with a O(V³) sequential implementation, a O(VE log(V²/E)) implementation using dynamic trees, and parallel/distributed implementation. Goldberg–Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and Uzi Vishkin. The idea of a preflow was originally conceived by Alexander V. This pre-flow algorithm also used a push operation; however, it used distances in the auxiliary network to determine where to push the flow instead of a labeling system. The push–relabel algorithm uses a nonnegative integer valid labeling function which makes use of distance labels, or heights, on nodes to determine which arcs should be selected for the push operation.
Reader's Guide
The push–relabel algorithm is significant as one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial O(V²E) time complexity, which is asymptotically more efficient than the O(VE²) Edmonds–Karp algorithm. Specific variants achieve even lower time complexities: the variant based on the highest label node selection rule has O(V²√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic O(VE log(V²/E)) time complexity can be achieved using dynamic trees, although in practice it is less efficient. The algorithm has been extended to compute minimum cost flows. The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance. The algorithm maintains a valid labeling function throughout execution, ensuring that if a preflow and valid labeling exist, there is no augmenting path from source to sink in the residual graph. The algorithm terminates when all nodes except source and sink have no excess flow, converting the preflow into a maximum flow.
Did You Know?
- The push–relabel algorithm is also known as the preflow–push algorithm.
- The generic algorithm has a strongly polynomial O(V²E) time complexity.
- The variant based on the highest label node selection rule has O(V²√E) time complexity.
Frequently Asked Questions
Who is Push–relabel maximum flow algorithm?
It is a method for finding the maximum flow through a directed flow network, also called the preflow–push algorithm. Rather than tracing augmenting paths from source to sink, it works by shuffling flow locally between adjacent vertices until a valid maximum flow emerges.
What are Push–relabel maximum flow algorithm's powers/role?
It repeatedly applies two local moves: a push operation that slides excess flow along an admissible edge to a neighbor, and a relabel operation that raises a vertex's height label when no admissible outgoing edge remains. This height-guided, node-by-node strategy is what distinguishes it from path-based flow methods.
How does Push–relabel maximum flow algorithm's story end?
The process stops the moment every node except the source and sink has zero excess flow, meaning the preflow has been fully converted into a legitimate flow. At that point the flow is provably maximum, and no further pushes or relabels are possible.
Why is Push–relabel maximum flow algorithm important?
It is widely regarded as one of the fastest practical maximum-flow methods, with a strongly polynomial O(V²E) worst-case bound. Its elegant reliance on purely local operations makes it both theoretically clean and highly competitive in real-world optimization workloads.
What is Push–relabel maximum flow algorithm's time complexity?
The algorithm is guaranteed to finish in O(V²E) time, where V is the number of vertices and E the number of edges. This strongly polynomial bound holds no matter which valid selection heuristic is used to pick the next active node.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record