RELABEL-TO-FRONT ALGORITHM

The 'relabel-to-front algorithm' finds the maximum flow in a flow network in $O(V^3)$ time. It is in the class of ''push-relabel algorithms'' for maximum flow which run in $O(V^2\; E)$. For dense graphs it is more efficient than the Edmonds-Karp algorithm, which runs in $O(VE^2)\; sube\; O(V^5)$ time.

Contents

Algorithm

Push

Relabel

Push-relabel algorithm

Discharge

Relabel-to-front algorithm

Sample implementation

References

Algorithm

Given a flow network $G(V,E)$ with capacity from node ''u'' to node ''v'' given as $c(u,v)$, and source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. Two types of operations are performed on nodes, ''push'' and ''relabel''. Throughout we maintain:

★ $f(u,v)$. Flow from ''u'' to ''v''. Available capacity is $c(u,v)\; -\; f(u,v)$.

★ $height(u)$. We only ''push'' from ''u'' to ''v'' if $height(u)\; >\; height(v)$

★ $excess(u)$. Sum of flow to and from ''u''.
After each step of the algorithm, the flow is a 'preflow', satisfying:

★ $f(u,v)\; leq\; c(u,v)$. The flow between $u$ and $v$ does not exceed the capacity.

★ $f(u,v)\; =\; -\; f(v,u)$. We maintain the net flow.

★ $sum\_v\; f(u,v)\; =\; excess(u)\; geq\; 0$ for all nodes $u$
eq s. Only the source may produce flow.
Notice that the last condition for a preflow is relaxed from the corresponding condition for a legal flow in a regular flow network.
We observe that the longest possible path from ''s'' to ''t'' is $|V|$ nodes long. Therefore it must be possible to assign ''height'' to the nodes such that for any legal flow, $height(s)\; =\; |V|$ and $height(t)\; =\; 0$, and if there is a positive flow from ''u'' to ''v'', $height(u)\; >\; height(v)$. As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as Ford-Fulkerson, the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.
In short words, the heights of nodes (except ''s'' and ''t'') is adjusted, and flow is sent between nodes, until all possible flow has reached ''t''. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach ''t'', has flowed back into ''s''. A node can reach the height $2|V|-1$ before this is complete, as the longest possible path back to ''s'' excluding ''t'' is $|V|-1$ long, and $height(s)\; =\; |V|$. The height of ''t'' is kept at 0.

Push

A ''push'' from ''u'' to ''v'' means sending a part of the excess flow into ''u'' on to ''v''. Three conditions must be met for a ''push'' to take place:

★ $excess(u)\; >\; 0$. More flow into the node than out of it so far.

★ $c(u,v)\; -\; f(u,v)\; >\; 0$. Available capacity from ''u'' to ''v''.

★ $height(u)\; >\; height(v)$. Can only send to lower node.
We send an amount of flow equal to $min(excess(u),\; c(u,v)-f(u,v))$.

Relabel

Doing a ''relabel'' on a node ''u'' is increasing its height until it is higher than at least one of the nodes it has available capacity to. Conditions for a ''relabel'':

★ $excess(u)\; >\; 0$. There must be a point in relabelling.

★ $height(u)\; leq\; height(v)$ for all ''v'' such that $c(u,v)-f(u,v)\; >\; 0$. The only nodes we have available capacity to are higher.
When relabelling ''u'', we set $height(u)$ to be the lowest value such that $height(u)\; >\; height(v)$ for some ''v'' where $c(u,v)-f(u,v)\; >\; 0$.

Push-relabel algorithm

''Push-relabel algorithms'' in general have the following layout:
# As long as there is legal ''push'' or ''relabel'' operation
## Perform a legal push, or
## a legal relabel.
The running time for these algorithms are in general $O(V^2\; E)$ (argument omitted).

Discharge

In ''relabel-to-front'', a ''discharge'' on a node ''u'' is the following:
# As long as $excess(u)\; >\; 0$:
## If not all neighbours have been tried since last ''relabel'':
### Try to ''push'' flow to an untried neighbour.
## Else:
### ''Relabel'' ''u''
This requires that for each node, it is known which nodes have been tried since last ''relabel''.

Relabel-to-front algorithm

In the ''relabel-to-front algorithm'', the order of the ''push'' and ''relabel'' operations is given:
# Send as much flow from ''s'' as possible.
# Build a list of all nodes except ''s'' and ''t''.
# As long as we have not traversed the entire list:
## ''Discharge'' the current node.
## If the height of the current node changed:
### Move the current node to the front of the list
### Restart the traversal from the start of the list.
The running time for ''relabel-to-front'' is $O(V^3)$ (proof omitted).

Sample implementation

Python implementation:
'def' relabel_to_front(C, source, sink):
n = len(C) ''# C is the capacity matrix''
F =