Push–relabel maximum flow algorithm
In mathematical optimization, the push–relabel algorithm is an algorithm for computing maximum flows in a flow network. The name "push–relabel" comes from the two basic operations used in the 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 push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a strongly polynomial time complexity, which is asymptotically more efficient than the Edmonds–Karp algorithm. Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic time complexity can be achieved using dynamic trees, although in practice it is less efficient.
The push–relabel 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.
History
A preflow is a flow in which the total amount flowing into a vertex may be greater than the total amount flowing out of it, allowing an algorithm to change the flow on a single arc. This idea was originally conceived by Alexander V. Karzanov and was published in 1974 in Soviet Mathematical Dokladi 15. 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 was designed by Andrew V. Goldberg and Robert Tarjan. The algorithm was initially presented in November 1986 in STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, and then officially in October 1988 as an article in the Journal of the ACM. Both papers detail a generic form of the algorithm terminating in along with a sequential implementation, a implementation using dynamic trees, and parallel/distributed implementation. As explained in, Goldberg–Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and Uzi Vishkin.
Concepts
Definitions and notations
Let:- be a network with capacity function,
- a flow network, where and are chosen source and sink vertices respectively,
- denote a pre-flow in,
- denote the excess function with respect to the flow, defined by,
- denote the residual capacity function with respect to the flow, defined by,
- being the edges where,
- denote the residual network of with respect to the flow.
In the algorithm, the label values of and are fixed. is a lower bound of the unweighted distance from to in if is reachable from. If has been disconnected from, then is a lower bound of the unweighted distance from to. As a result, if a valid labeling function exists, there are no paths in because no such paths can be longer than.
An arc is called admissible if. The admissible network is composed of the set of arcs that are admissible. The admissible network is acyclic.
For a fixed flow, a vertex is called active if it has positive excess with respect to, i.e.,.
Operations
Initialization
The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs exiting the source, where. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph,, and all other nodes are given a label of zero. Once the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.Push
The push operation applies on an admissible out-arc of an active node in. It moves units of flow from to.push:
assert xf > 0 and ? ? + 1
Δ = min
f += Δ
f -= Δ
xf -= Δ
xf += Δ
A push operation that causes to reach is called a saturating push since it uses up all the available capacity of the residual arc. Otherwise, all of the excess at the node is pushed across the residual arc. This is called an unsaturating or non-saturating push.
Relabel
The relabel operation applies on an active node which is neither the source nor the sink without any admissible out-arcs in. It modifies to be the minimum value such that an admissible out-arc is created. Note that this always increases and never creates a steep arc, which is an arc such that, and.relabel:
assert xf > 0 and ? <= ? for all v such that cf > 0
? = 1 + min
Effects of push and relabel
After a push or relabel operation, remains a valid labeling function with respect to.For a push operation on an admissible arc, it may add an arc to, where ; it may also remove the arc from, where it effectively removes the constraint.
To see that a relabel operation on node preserves the validity of, notice that this is trivially guaranteed by definition for the out-arcs of u in. For the in-arcs of in, the increased can only satisfy the constraints less tightly, not violate them.
The generic push–relabel algorithm
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 generic version of the algorithm will terminate in.Since,, and there are no paths longer than in, in order for to satisfy the valid labeling condition must be disconnected from. At initialisation, the algorithm fulfills this requirement by creating a pre-flow that saturates all out-arcs of, after which is trivially valid for all. After initialisation, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the pre-flow has been converted into a maximum flow.
generic-push-relabel:
create a pre-flow f that saturates all out-arcs of s
let ? = |V|
let ? = 0 for all v ∈ V \
while there is an applicable push or relabel operation do
execute the operation
Correctness
The algorithm maintains the condition that is a valid labeling during its execution. This can be proven true by examining the effects of the push and relabel operations on the label function. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the constraint. The push operation can send flow from to if. This may add to and may delete from. The addition of to will not affect the valid labeling since. The deletion of from removes the corresponding constraint since the valid labeling property only applies to residual arcs in.If a preflow and a valid labeling for exists then there is no augmenting path from to in the residual graph. This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist. If the algorithm terminates, then all nodes in are not active. This means all have no excess flow, and with no excess the preflow obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to the max-flow min-cut theorem since there is no augmenting path from to.
Therefore, the algorithm will return the maximum flow upon termination.
Time complexity
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. The numbers of relabel, saturating push and nonsaturating push operations are analyzed separately.In the algorithm, the relabel operation can be performed at most times. This is because the labeling value for any node u can never decrease, and the maximum label value is at most for all nodes. This means the relabel operation could potentially be performed times for all nodes . This results in a bound of for the relabel operation.
Each saturating push on an admissible arc removes the arc from. For the arc to be reinserted into for another saturating push, must first be relabeled, followed by a push on the arc, then must be relabeled. In the process, increases by at least two. Therefore, there are saturating pushes on, and the total number of saturating pushes is at most. This results in a time bound of for the saturating push operations.
Bounding the number of nonsaturating pushes can be achieved via a potential argument. We use the potential function . It is obvious that is initially and stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase. 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. This means that over the execution of the algorithm, the nonsaturating pushes must make up the difference of the relabel and saturating push operations in order for to terminate with a value of 0.
The relabel operation can increase by at most. A saturating push on activates if it was inactive before the push, increasing by at most. Hence, the total contribution of all saturating pushes operations to is at most. A nonsaturating push on always deactivates, but it can also activate as in a saturating push. As a result, it decreases by at least. Since relabels and saturating pushes increase, the total number of nonsaturating pushes must make up the difference of. This results in a time bound of for the nonsaturating push operations.
In sum, the algorithm executes relabels, saturating pushes and nonsaturating pushes. Data structures can be designed to pick and execute an applicable operation in time. Therefore, the time complexity of the algorithm is.