Network Flow: Push-relabel algorithm

According to CLRS: Many of the asymptotically fastest maximum-flow algorithms are push-relabel algorithms, and the fastest actual implementations of maximum-flow algorithms are based on the push-relabel method. Push-relabel methods also efficiently solve other flow problems, such as the minimum-cost flow problem.

This algorithm has a very different flavor. The overall idea is to generate a ‘preflow’ that may not satisfy the flow properties, and keep ‘pushing’) and ‘elevating’ (relabelling) the vertices until we cannot do that. We then remove the ‘excess’ from the preflow and obtain a valid flow, which is also a max flow. In particular, the in-flow may be larger than out-flow at a vertex. The amount of overflow is called ‘excess’.

The intuition behind is this: think of the vertices as platforms that have different height, where initially \(S\) has \(\vert V\vert\) height and all other vertices have 0 heights. The flow can only be pushed from higher vertices to lower vertices. Whenever we do not have any flow to push, we find some vertex that has unsaturated out edge to its neighbor vertices to ‘relabel’, i.e., elevating its height such that we can continue to ‘push’. Thus, there are two operations ‘push’ and ‘relabel’ (and thus the name):

push: sending excess from u to v
relabel: increase the height of u to min({v: neighbor of u})+1

The algorithm is as follows:

Initialize s.h = |V|, u.h = 0 for u != s. // u.h is the height of vertex u
For all (s, u), push c(s, u). // saturate all outgoing edges from s.
While there is vertex that can be pushed or relabel
  do push or relabel
End while
return F.

The naive implementation has runtime \(O(\vert V\vert ^2 \vert E\vert )\), and can be improved to \(O(\vert V\vert ^3)\).