5.2.3. The Highest-Vertex Preflow-Push Algorithm*

The highest-vertex preflow-push algorithm is the final version of the preflow-push algorithm we discuss. It achieves a running time of \(O\bigl(n^2 \sqrt{m}\bigr)\), which improves on the relabel-to-front algorithm by a factor of up to \(O\bigl(\sqrt{n}\bigr)\). Just as the relabel-to-front algorithm, the algorithm uses Discharge operations to push flow from vertices to their neighbours.¹ While the relabel-to-front algorithm picks vertices to discharge based on the order of vertices in \(L\), the highest-vertex preflow-push algorithm always picks an overflowing vertex with maximum height to be discharged next. Hence its name.

To support picking vertices to discharge based on their heights, we organize \(L\) as an array of linked lists. The \(i\)th linked list stores all overflowing vertices of height \(i\). We also store a height bound \(h_{\textrm{max}}\) and maintain the invariant that all overflowing vertices have height at most \(h_{\textrm{max}}\). Initially, we set \(h_{\textrm{max}} = 0\), which satisfies the invariant because \(s\) does not overflow and any other vertex has height \(0\). To find the next vertex to discharge, we apply the following strategy: As long as \(h_{\textrm{max}} \ge 0\) and there is no overflowing vertex of height \(h_{\textrm{max}}\), we decrease \(h_{\textrm{max}}\) by one. Note that this maintains the property that there is no overflowing vertex of height greater than \(h_{\textrm{max}}\). Thus, if this decreases \(h_{\textrm{max}}\) below zero, then there exists no overflowing vertex and the algorithm exits.

If we stop at a value \(h_{\textrm{max}} \ge 0\), then there exists an overflowing vertex of height \(h_{\textrm{max}}\). We pick such a vertex \(x\), call \(\boldsymbol{\textbf{Discharge}(x)}\), and then repeat the above search for the next vertex to discharge until we finally reach the condition \(h_{\textrm{max}} < 0\).

When calling \(\boldsymbol{\textbf{Discharge}(x)}\) for some vertex \(x\), then \(x\) has height \(h_{\textrm{max}}\) and no overflowing vertex has height greater than \(h_{\textrm{max}}\). Every time \(\boldsymbol{\textbf{Discharge}(x)}\) relabels \(x\), we set \(h_{\textrm{max}} = h_x\) because \(x\) is still overflowing at the time it is relabelled and it is thus the highest overflowing vertex. Every time we push flow from \(x\) to a neighbour \(y\), this makes \(y\)'s excess positive. Thus, we insert \(y\) into the \(h_y\)th list in \(L\) if \(y\)'s excess was not already positive before the Push operation. Note that this does not require an update of \(h_{\textrm{max}}\) because \(x\) has height \(h_{\textrm{max}}\) at any time during the \(\boldsymbol{\textbf{Discharge}(x)}\) operation and, since we push flow from \(x\) to \(y\) only if \(h_y = h_x - 1 < h_{\textrm{max}}\), \(y\) has height less than \(h_{\textrm{max}}\).

On the input graph in Figure 5.1, the highest-vertex preflow-push algorithm performs the same sequence of Push operations as the relabel-to-front algorithm, illustrated in Figure 5.17. The correctness of the algorithm follows immediately because the algorithm returns only once \(h_{\textrm{max}} < 0\), that is, once there is no overflowing vertex left. At this point, \(f\) is a feasible \(st\)-flow. Since the highest-vertex preflow-push algorithm is a variant of the generic preflow-push algorithm, Theorem 5.17 shows that \(f\) is a maximum \(st\)-flow at this point.