Push–relabel maximum flow algorithm
Throughout its execution, the algorithm 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.
In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.
The variant based on the highest label node selection rule has O(V 2√E) time complexity and is generally regarded as the benchmark for maximum flow algorithms.
[3][4] Subcubic O(VElog(V 2/E)) time complexity can be achieved using dynamic trees,[2] although in practice it is less efficient.
[citation needed] The push–relabel algorithm has been extended to compute minimum cost flows.
[4][6] The concept of a preflow was originally designed by Alexander V. Karzanov and was published in 1974 in Soviet Mathematical Dokladi 15.
[2][8] As explained in,[9] Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and Uzi Vishkin.
This function must satisfy the following conditions in order to be considered valid: In the algorithm, the label values of s and t are fixed.
For a fixed flow f, a vertex v ∉ {s, t} is called active if it has positive excess with respect to f, i.e., xf (u) > 0.
The push operation applies on an admissible out-arc (u, v) of an active node u in Gf.
The relabel operation applies on an active node u which is neither the source nor the sink without any admissible out-arcs in Gf.
To see that a relabel operation on node u preserves the validity of 𝓁(u), notice that this is trivially guaranteed by definition for the out-arcs of u in Gf.
For the in-arcs of u in Gf, the increased 𝓁(u) can only satisfy the constraints less tightly, not violate them.
The generic push–relabel algorithm is used as a proof of concept only and does not contain implementation details on how to select an active node for the push and relabel operations.
This can be proven true by examining the effects of the push and relabel operations on the label function 𝓁.
[8] If a preflow f and a valid labeling 𝓁 for f exists then there is no augmenting path from s to t in the residual graph Gf .
This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist.
In order to bound the time complexity of the algorithm, we must analyze the number of push and relabel operations which occur within the main loop.
However, the value of Φ must be equal to 0 at termination since there cannot be any remaining active nodes at the end of the algorithm's execution.
Data structures can be designed to pick and execute an applicable operation in O(1) time.
[1][8] The following is a sample execution of the generic push-relabel algorithm, as defined above, on the following simple network flow graph diagram.
In the example, the h and e values denote the label 𝓁 and excess xf , respectively, of the node during the execution of the algorithm.
The "current-arc" data structure is a mechanism for visiting the in- and out-neighbors of a node in the flow network in a static circular order.
Therefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node
Depending on the selection rule, the algorithm exhibits different time complexities.
The algorithm scans the list from front to back and performs a discharge operation on the current node if it is active.
[3] Although in the description of the generic push–relabel algorithm above, 𝓁(u) is set to zero for each node u other than s and t at the beginning, it is preferable to perform a backward breadth-first search from t to compute exact labels.
The global relabeling heuristic periodically performs backward breadth-first search from t in Gf to compute the exact labels of the nodes.
Both heuristics skip unhelpful relabel operations, which are a bottleneck of the algorithm and contribute to the ineffectiveness of dynamic trees.
