5.2.2.4. Correctness of the Algorithm

The last thing to prove is that the relabel-to-front algorithm correctly computes a maximum \(st\)-flow. To this end, we show that the algorithm maintains the following invariant. Let the admissible subgraph \(G^{f,h} = \bigl(V, E^{f,h}\bigr)\) of the residual network \(G^f\) be the subgraph of \(G^f\) whose edge set \(E^{f,h}\) consists of all admissible edges in \(G^f\).

Invariant 5.29: The list \(L\) is a topological ordering of \(G^{f,h}\) and there is no overflowing vertex that precedes the current vertex \(x\) in \(L\).

At the end of the algorithm, \(x\) points one position beyond the end of \(L\), so the invariant states that, at this time, no vertex in \(L\) is overflowing. As shown in the proof of Theorem 5.17, this implies that the edge labelling \(f\) returned by the algorithm is a maximum \(st\)-flow. It remains to prove the invariant.

Proof: Initially, \(h_s = n\) and \(h_x = 0\) for all \(x \ne s\). Since \(n \ge 2\) (\(G\) contains at least \(s\) and \(t\)), there is no edge whose endpoints have heights that differ by exactly one, that is, \(E^{f,h} = \emptyset\). Thus, the arbitrary ordering of the vertices in \(L\) chosen initially is a topological ordering of \(G^{f,h}\). Since \(x\) is the first vertex in \(L\), there is no vertex that precedes \(x\) in \(L\). In particular, no overflowing vertex precedes \(x\) in \(L\).

Next consider the effect of discharging a vertex \(x\) and advancing \(x\) to the next vertex in \(L\). For the sake of clarity, we refer to the value of \(x\) at the beginning of the current iteration as \(x_{\textrm{old}}\) and to the value of \(x\) after the current iteration as \(x_{\textrm{new}}\). We distinguish two cases:

• If \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) relabels \(x_{\textrm{old}}\), then \(x_{\textrm{old}}\) is moved to the front of \(L\), so there is no overflowing vertex that precedes \(x_{\textrm{old}}\) in \(L\). Since \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) leaves \(x_{\textrm{old}}\) without excess flow, advancing \(x\) from \(x_{\textrm{old}}\) to \(x_{\textrm{new}}\) after the \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) operation returns maintains the invariant that there is no overflowing vertex that precedes \(x\) in \(L\).

  By Lemma 5.25, Push operations performed by \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) do not create any admissible edges. By Lemma 5.26, the only admissible edges created by relabelling \(x_{\textrm{old}}\) are out-edges of \(x_{\textrm{old}}\). Thus, since \(L\) was a topological ordering of \(G^{f,h}\) before calling \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\), it remains a topological ordering of \(G^{f,h}\) immediately after \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) returns but before moving \(x_{\textrm{old}}\) to the front of \(L\), except that the ordering may violate some out-edges of \(x_{\textrm{old}}\).

  By moving \(x_{\textrm{old}}\) to the front of \(L\), we ensure that the out-edges of \(x_{\textrm{old}}\) are respected by \(L\). By Lemma 5.26, \(x_{\textrm{old}}\) has no admissible in-edges immediately after relabelling \(x_{\textrm{old}}\). By Lemma 5.25, the Push operations performed by \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) between the last \(\boldsymbol{\textbf{Relabel}(x_{\textbf{old}})}\) operation and the return of \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) cannot make any in-edges of \(x_{\textrm{old}}\) admissible. Thus, \(x_{\textrm{old}}\) has no admissible in-edges after \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) returns and \(L\) is a topological ordering of \(G^{f,h}\) after moving \(x_{\textrm{old}}\) to the front of \(L\).

• If \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) does not relabel \(x_{\textrm{old}}\), then the ordering of \(L\) is not changed and \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) performs only Push operations. By Lemma 5.25, Push operations do not create any admissible edges. Thus, \(L\) remains a topological ordering of \(G^{f,h}\).

  After advancing \(x\) to \(x_{\textrm{new}}\), the vertices preceding \(x\) in \(L\) are \(x_{\textrm{old}}\) and the vertices that precede \(x_{\textrm{old}}\) in \(L\). Since \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) leaves \(x_{\textrm{old}}\) without excess flow, this implies that any overflowing vertex \(y\) that precedes \(x_{\textrm{new}}\) must be a vertex that precedes \(x_{\textrm{old}}\) in \(L\). Since there was no overflowing vertex that preceded \(x_{\textrm{old}}\) before the call to \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\), this Discharge operation must push some flow from \(x_{\textrm{old}}\) to \(y\). Since \(\boldsymbol{\textbf{Discharge}(x_{\textbf{old}})}\) pushes flow only along admissible edges, the edge \((x_{\textrm{old}}, y)\) is thus admissible, a contradiction because \(y\) precedes \(x_{\textrm{old}}\) in \(L\) and \(L\) is a topological ordering of \(G^{f,h}\). This shows that no vertex preceding \(x_{\textrm{new}}\) in \(L\) is overflowing. ▨

As argued above, the relabel-to-front algorithm correctly computes a maximum \(st\)-flow. By Lemma 5.28, its running time is \(O\bigl(n^3\bigr)\). Thus, we obtain the following result:

Theorem 5.30: The relabel-to-front algorithm computes a maximum flow in \(O\bigl(n^3\bigr)\) time.