5.2.2. The Relabel-To-Front Algorithm*

One characteristic of the generic preflow-push algorithm is that it delays Relabel operations for as long as possible: As long as there exists an overflowing vertex \(x\) with an admissible out-edge \((x, y)\), it prefers to push flow from \(x\) to \(y\) along this edge over relabelling a vertex.

We call an edge \((x, y)\) admissible if \(u^f_{x,y} > 0\) and \(h_x = h_y + 1\), that is, if we can push flow along this edge.

This is a natural strategy because the main goal of the algorithm is to push flow along edges, not to relabel vertices. In addition, as discussed in Exercise 5.2, Push operations are cheaper than Relabel operations. Nevertheless, it turns out that once we decide to reduce the excess at some vertex \(x\) by pushing flow from \(x\) to its neighbours, it is beneficial to completely eliminate \(x\)'s excess, if necessary by relabelling \(x\) even though there may still exist admissible edges elsewhere in the graph. This idea leads to the relabel-to-front algorithm, which achieves a running time of \(O\bigl(n^3\bigr)\). The relabel-to-front algorithm is a variant of the generic preflow-push algorithm: It simply chooses the order in which to perform Push and Relabel operations more carefully (and chooses the right data structures to maintain its state). Thus, it is a correct maximum flow algorithm.

Note that the generic preflow-push algorithm almost achieves an \(O\bigl(n^3\bigr)\) running time already. The only reason its running time may be as high as \(O\bigl(n^2m\bigr)\) is because this is the number of non-saturating Push operations it may perform. The goal of the relabel-to-front algorithm is thus to reduce the number of these operations to \(O\bigl(n^3\bigr)\).