# The push-relabel algorithm

### Preliminaries

Let be a directed graph with a source and a sink , . Let be the number of nodes and be the number of edges. Let be a capacity function that assigns nonnegative weights to the edges of the graph.

We want to compute a maximum flow in 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 . Therefore we start the computation with some preflow and with a valid labelling . Mostly the preflow is used with for all and for all other edges . For this preflow we can choose, e.g., and for all nodes as a valid labelling. In any further step the existing preflow is pushed towards or is reduced until the preflow becomes an 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 let denote the edge with reversed direction. Further let .
Then, to each edge we assign a so-called residual capacity

This residual capacity shows how much we can change the preflow on an edge without violating the capacity constraint .

An edge is called residual edge if it has a positive residual capacity . If denotes the set of all residual edges, the graph is called residual graph of .

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

### Definition Flow Excess

A node is called*active*if it has a positive flow excess .

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

- PUSH(v,w):

- Let .
- The flow of an edge is increased by if .
- If the edge is an edge with reversed direction then the flow on the edge is reduced by .
- Anyway the flow excess of the nodes has to be updated.

The operation PUSH is applicable to an edge if is active, , and .

- RELABEL(v):

- Set .

The operation RELABEL is applicable to a node if is active and for all residual edges .

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

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

#### Lemma 1

If is a preflow, is a valid labelling, and is an active node, then either the push or the relabel operation is applicable to either a residual edge .Now we can give an estimation how often the operations PUSH and RELABEL can be applied before the flow excess is zero for all nodes and the algorithm terminates.

#### Lemma 2

The number of relabelling operations is at most per node and at most overall. The number of push operations is at most .

Thus, the push-relabel algorithm terminates after 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 , are finite at termination. Then the preflow is a maximum flow.

### Example

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

- Error creating thumbnail: File missing

In the following figures changes are marked in red and the valid labelings are given.

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

- Error creating thumbnail: File missing

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

- Error creating thumbnail: File missing

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

- Error creating thumbnail: File missing

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

- Error creating thumbnail: File missing

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

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)].