The push-relabel algorithm

From Cophy
Jump to: navigation, search

Contents


Preliminaries

Let G = (V,E) be a directed graph with a source s ∈ V  and a sink t ∈ V,  s ≠ t. Let n = | V | be the number of nodes and m = | E | be the number of edges. Let c:\ E\ \rightarrow\ \mathbb{R_+} be a capacity function that assigns nonnegative weights to the edges of the graph.

We want to compute a maximum flow in G  by using the push-relabel algorithm of [Goldberg and Tarjan (1986)].

The idea of the algorithm is to push as much flow as we can through the given graph G. Therefore we start the computation with some preflow f:\ E\ \rightarrow\ \mathbb{R} and with a valid labelling d:\ V\ \rightarrow\ \mathbb{N}\ \cup\ \{0,\infty\}. Mostly the preflow f  is used with f(s,v) = c(s,v) for all (s,v) ∈ E and f(e) = 0 for all other edges e ∈ E. For this preflow we can choose, e.g., d(s) = n and d(v) = 0 for all nodes v ∈ V \{s} as a valid labelling. In any further step the existing preflow is pushed towards t or is reduced until the preflow becomes an st flow.

To explain the algorithm we have to introduce some basic notations.

Suppose we have pushed a specific amount of flow from the source to the sink. In order to increase the amount of flow reaching the sink, we might to increase the flow on some and decrease it on other edges. Roughly speaking, a residual graph is used to encode these possible changes.
For each e = (v,u) ∈ E  let e − 1 = (u,v denote the edge with reversed direction. Further let E − 1 = {e − 1e ∈ E}. Then, to each edge e ∈ E ∪ E − 1 we assign a so-called residual capacity

r_f(e) =
\begin{cases}
c(e) - f(e), & if\ e\ \in\ E \\
f(e^{-1}), & if\ e\ \in\ E^{-1}.
\end{cases}

This residual capacity shows how much we can change the preflow on an edge e  without violating the capacity constraint 0 ≤ f(e) ≤ c(e).
An edge e ∈ E ∪ E − 1 is called residual edge if it has a positive residual capacity rf (e) > 0. If Ef  denotes the set of all residual edges, the graph Gf = (V,Ef ) is called residual graph of f.

Furthermore, the difference between the total preflow into a node v  and the total preflow out of this node is called flow excess ef of the node v ∈ V.

Definition Flow Excess

A node v ∈ V \{s,t} is called active if it has a positive flow excess ef (v) > 0.


The push-relabel algorithm repetitively performs the basic operations PUSH and RELABEL while there exists an active node.

  • PUSH(v,w):
Let δ : = min{ef (v), rf (v,w) }.
The flow of an edge (v,w) is increased by δ if (v,w) ∈ E.
If the edge (v,w) is an edge with reversed direction then the flow on the edge (w,v) is reduced by δ.
Anyway the flow excess of the nodes v,w ∈ V has to be updated.

The operation PUSH is applicable to an edge (v,w) ∈ Ef  if v  is active, rf (v,w) > 0, and d(v) = d(w) + 1.

  • RELABEL(v):
Set d(v): = min{d(w) + 1: (v,w) ∈ Ef}.

The operation RELABEL is applicable to a node v ∈ V if v is active and d(v) ≤ d(w) for all residual edges (v,w) ∈ Ef.

While the operations PUSH and RELABEL are performed, f  remains a preflow and d  a valid labelling for f. Furthermore, the valid labellings d(v never decrease for all nodes v ∈ V. If the operation RELABEL(v) is applied to v, the value d(v increases.

The next lemma ensures that one of the operations can be applied while there exists some active node.

Lemma 1

If f is a preflow, d is a valid labelling, and v is an active node, then either the push or the relabel operation is applicable to either a residual edge (v,wor to v.

Now we can give an estimation how often the operations PUSH and RELABEL can be applied before the flow excess ef (v) is zero for all nodes and the algorithm terminates.

Lemma 2

The number of relabelling operations is at most 2n − 1 per node and at most (n − 2)(2n − 1) overall. The number of push operations is at most 2nm + 4n2m.


Thus, the push-relabel algorithm terminates after O(n2m) basic operations.The correctness of the push-relabel algorithm is guaranteed by the following theorem.

Theorem 3

Suppose that the algorithm terminates and all labels d(v), v ∈ V, are finite at termination. Then the preflow f is a maximum flow.


Example

We want to determine a maximum flow on the following graph. The edges are labeld (ce,fe) denoting the edge capacity and the current flow on this edge.


Push relabel algo example graph 1.jpg


In the following figures changes are marked in red and the valid labelings d(v), vV are given.

We start the push-relabel algorithm with the following standart preflow and labelling:


Push relabel algo example graph 2.jpg


The nodes aband d are active. Applying the operations RELABEL(a) and PUSH(a,t) yields d(a) = 1 and f(a,t) = 1. If we execute RELABEL(b) and PUSH(b,c), then it is d(b) = 1 and f(b,c) = 1. Now we have the following preflow and relabelling:


Push relabel algo example graph 3.jpg


The node b is still active. But the only outgoing edge from b in the residual graph Ef is (b,s). Thus using RELABEL(b) and PUSH(b,s) we obtain d(b) = 7 and f(s,b) = 1. Now we consider the active node d. Applying the basic operations on that node results in d(d) = 2 and f(d,a) = 1. We obtain the following preflow and relabelling:


Push relabel algo example graph 4.jpg


The node a is active again. We cannot apply the relabel operation, but the operation PUSH(a,c). Then it is f(a,c) = 1. Now, c is the only active node. We apply RELABEL(c) and PUSH(c,t). This results in the following preflow and relabelling:


Push relabel algo example graph 5.jpg


Since all nodes are not active, the algorithm terminates. The computed preflow f is a maximum flow with the value | f | = 3.


If some valid labelling for a maximum flow is known, it can be used for computing a minimum s-t cut.

For more details we refer the interested reader to the report on the push-relabel algorithm by [Goldberg et al. (1986)].

Personal tools