5.2.3.1. Running Time Analysis

We divide the analysis of the running time of the highest-vertex preflow-push algorithm into three parts:

• The first part shows that the cost of Relabel and saturating Push operations is \(O(nm)\). (This bound in fact holds for every variant of the generic preflow-push algorithm, but a bound of \(O\bigl(n^3\bigr)\) was sufficient before.)

• The second part of the analysis shows that the highest-vertex preflow-push algorithm performs only \(O\bigl(n^2\sqrt{m}\bigr)\) non-saturating Push operations. As for the generic preflow-push algorithm and for the relabel-to-front algorithm, bounding the number of non-saturating Push operations is the hardest part of the analysis. Since the cost of each such operation is constant, by Exercise 5.2, the cost of these operations is thus \(O\bigl(n^2\sqrt{m}\bigr)\).

• The third part of the analysis shows that the cost of searching \(L\) for the next vertex to be discharged is also \(O\bigl(n^2\sqrt{m}\bigr)\).

Since \(nm \in O\bigl(n^2\sqrt{m}\bigr)\), the cost of the highest-vertex preflow-push algorithm is thus \(O\bigl(n^2\sqrt{m}\bigr)\), as claimed.

Lemma 5.31: The cost of Relabel and saturating Push operations performed by any variant of the generic preflow-push algorithm is \(O(nm)\).

Proof: By Lemma 5.21, the algorithm performs \(O(nm)\) saturating Push operations. Since each such operation takes constant time, by Exercise 5.2, their total cost is \(O(nm)\).

You proved in Exercise 5.2 that the cost of a \(\boldsymbol{\textbf{Relabel}(x)}\) operation is \(O(n)\). If you performed this analysis carefully, you observed that the cost is in fact \(O(\deg(x))\), which is \(O(n)\) because \(\deg(x) < n\). Since every vertex is relabelled at most \(2n\) times, as shown in the proof of Lemma 5.20, the total cost of Relabel operations is thus \(\sum_{x \in V} O(n\deg(x)) = O(nm)\). ▨

Lemma 5.32: The highest-vertex preflow-push algorithm performs \(O\bigl(n^2\sqrt{m}\bigr)\) non-saturating Push operations.

Proof: The analysis uses a potential function \(\Phi\). For every node \(x \in V\), let

\[\ell_x = \bigl|\bigl\{y \in V \mid h_y \le h_x\bigr\}\bigr|\]

be the number of vertices whose heights are no greater than \(x\)'s. Let

\[A = \{ x \in V \setminus \{s, t\} \mid e_x > 0 \}\]

be the set of active vertices, that is, the set of vertices other than \(s\) or \(t\) with positive excess. Then

\[\Phi = \frac{1}{k} \sum_{x \in A} \ell_x,\]

for some parameter \(k\) to be defined later.

Note that \(\Phi \le \frac{n^2}{k}\) initially. Next we consider the effect of Relabel and Push operations on \(\Phi\).

A Push operation does not change the height of any vertex, so \(\ell_x\) remains unchanged for all \(x \in V\). If the Push operation along an edge \((x, y)\) is saturating, then \(x\) remains active and \(y\) may become active if it was not active before. These are the only changes to \(A\). Thus, \(\Phi\) increases by at most \(\frac{\ell_y}{k} \le \frac{n}{k}\). If the Push operation is non-saturating, then again \(\Phi\) increases by at most \(\frac{\ell_y}{k}\) and decreases by \(\frac{\ell_x}{k}\) because \(e_x = 0\) after a saturating \(\boldsymbol{\textbf{Push}(x, y)}\) operation. Since \(h_y = h_x - 1\), we have \(\ell_y < \ell_x\), so \(\Phi\) decreases.

A \(\boldsymbol{\textbf{Relabel}(x)}\) operation increases \(h_x\). This does not change \(A\) and does not increase \(\ell_y\) for any vertex \(y \ne x\). \(\ell_x\) increases by at most \(n\), so \(\Phi\) increases by at most \(\frac{n}{k}\).

Now consider the sequence of Push and Relabel operations the algorithm performs. A phase is a maximal contiguous subsequence of operations during which \(h_{\textrm{max}}\) remains unchanged. We call a phase cheap if it performs at most \(k\) non-saturating Push operations. Otherwise, it is expensive.

Note that \(h_{\textrm{max}} = 0\) initially and increases only as a result of relabelling a vertex \(x\) with \(h_x = h_{\textrm{max}}\). By Lemma 5.20, \(h_{\textrm{max}}\) increases at most \(2n^2\) times. Moreover, the proof of Lemma 5.20 shows that the total increase of \(h_{\textrm{max}}\) over all Relabel operations is at most \(2n^2\). Thus, since \(h_{\textrm{max}}\) remains non-negative while the algorithm runs, \(h_{\textrm{max}}\) also decreases at most \(2n^2\) times. In total, \(h_{\textrm{max}}\) changes at most \(4n^2\) times, so there are at most \(4n^2\) phases. The total number of non-saturating Push operations in cheap phases is therefore at most \(4n^2k\).

For an expensive phase, observe that all Push operations originate at vertices \(x\) with \(h_x = h_{\textrm{max}}\) and no vertices are relabelled during the phase. A non-saturating Push operation originating at a vertex \(x\) deactivates \(x\). In order to perform another non-saturating Push operation from \(x\) to one of its neighbours, \(x\) has to be reactivated, which happens only if \(x\) receives flow from one of its neighbours. However, \(h_x = h_{\textrm{max}}\), we push flow only from vertices with height \(h_{\textrm{max}}\) during this phase, and we push flow only along edges \((y, z)\) with \(h_y = h_z + 1\). Thus, \(x\) does not receive any flow during the current phase and can be the source of at most one non-saturating Push operation in the current phase.

Since we perform more than \(k\) non-saturating Push operations in the current phase and no vertices are relabelled during this phase, this shows that there must exist \(q > k\) vertices of height \(h_{\textrm{max}}\) throughout this phase. Now, as observed above, a non-saturating Push operation along an edge \((x, y)\) decreases \(\Phi\) by \(\frac{\ell_x}{k}\) and increases it by at most \(\frac{\ell_y}{k}\). Since \(h_y = h_x - 1 = h_{\textrm{max}} - 1\), we have

\[\ell_x - \ell_y = |\{z \in V \mid h_z = h_{\textrm{max}}\}| = q.\]

Thus, every non-saturating Push operation in an expensive phase decreases \(\Phi\) by at least \(\frac{q}{k} > 1\).

By Lemmas 5.20 and 5.21, there are \(O(nm)\) Relabel and saturating Push operations and, as argued above, each such operation increases \(\Phi\) by at most \(\frac{n}{k}\) while non-saturating Push operations do not increase \(\Phi\). Thus, \(\Phi\) increases by \(O\Bigl(\frac{n^2m}{k}\Bigr)\) over the course of the algorithm. As observed above, \(\Phi \le \frac{n^2}{k} = O\Bigl(\frac{n^2m}{k}\Bigr)\) initially. Since every non-saturating Push operation in an expensive phase decreases \(\Phi\) by at least \(1\) and \(\Phi \ge 0\) at all times, this implies that the total number of non-saturating Push operations during expensive phases is \(O\Bigl(\frac{n^2m}{k}\Bigr)\).

By summing the number of non-saturating Push operations in cheap and expensive phases, we obtain a bound of \(O\Bigl(n^2k + \frac{n^2m}{k}\Bigr)\) on the total number of non-saturating Push operations. By choosing \(k = \sqrt{m}\), both terms in this sum become \(n^2\sqrt{m}\), that is, the algorithm performs \(O\bigl(n^2\sqrt{m}\bigr)\) non-saturating Push operations. ▨

Lemma 5.33: The cost of searching \(L\) for vertices to be discharged is \(O\bigl(n^2\sqrt{m}\bigr)\).

Proof: Let an iteration consist of decreasing \(h_{\textrm{max}}\) to find the maximum \(h_{\textrm{max}}\) such that \(h_{\textrm{max}} < 0\) or \(L[h_{\textrm{max}}]\) is non-empty, followed by the algorithm exiting or invoking \(\boldsymbol{\textbf{Discharge}(x)}\) for some vertex \(x \in L[h_{\textrm{max}}]\). Let \(h_i'\) be the value of \(h_{\textrm{max}}\) at the beginning of the \(i\)th iteration, and let \(h_i''\) be the value of \(h_{\textrm{max}}\) before the algorithm exits or invokes the \(\boldsymbol{\textbf{Discharge}(x)}\) operation in the \(i\)th iteration. Then the cost of searching \(L\) in the \(i\)th iteration is \(O(1 + \Delta_i)\), where \(\Delta_i = h_i' - h_i''\).

Since every iteration except the last performs a Discharge operation, the number of iterations is one more than the number of Discharge operations the algorithm performs. Since we invoke \(\boldsymbol{\textbf{Discharge}(x)}\) only on vertices \(x\) that overflow, every Discharge operation performs at least one Push operation. By Lemmas 5.21 and 5.32, we perform \(O\bigl(n^2\sqrt{m}\bigr)\) Push operations. Thus, we perform \(O\bigl(n^2\sqrt{m}\bigr)\) Discharge operations and the algorithm runs for \(r = O\bigl(n^2\sqrt{m}\bigr)\) iterations. The total cost of searching \(L\) across all \(r\) iterations is thus

\[\sum_{i=1}^r O(1 + \Delta_i) = O\bigl(n^2\sqrt{m}\bigr) + \sum_{i=1}^r O(\Delta_i).\]

Next we prove that

\[\sum_{i=1}^r \Delta_i = O\bigl(n^2\bigr).\]

Thus, the cost of searching \(L\) across all iterations is \(O\bigl(n^2\sqrt{m}\bigr)\).

To bound \(\sum_{i=1}^r \Delta_i\), we define a potential function

\[\Phi = h_{\textrm{max}} + 2n^2 - \sum_{x \in V} h_x.\]

Initially, \(\Phi \le 2n^2\) because \(h_{\textrm{max}} = 0\) and every vertex has a non-negative height. When the algorithm terminates, \(\Phi \ge 0\) because no vertex has height greater than \(2n - 1\) and \(h_{\textrm{max}} \ge -1\). Every decrease of \(h_{\textrm{max}}\) increases \(\sum_{i=1}^r \Delta_i\) by one and decreases \(\Phi\) by one. When relabelling a vertex \(x\), we have \(h_x = h_{\textrm{max}}\) before and after the Relabel operation. Thus, relabelling \(x\) does not change \(\Phi\), that is, \(\Phi\) never increases. This shows that

\[\sum_{i=1}^r \Delta_i \le 2n^2 = O\bigl(n^2\bigr).\ \text{▨}\]

We are now ready to state the result proven in this section:

Theorem 5.34: The highest-vertex preflow-push algorithm computes a maximum \(st\)-flow in an edge-weighted graph in \(O\bigl(n^2\sqrt{m}\bigr)\) time.