5.2.1.2. Running Time Analysis of the Generic Preflow-Push Algorithm

It remains to show that the preflow-push algorithm always terminates, quickly. The following lemma will be used to bound the maximum height a node can have:

Lemma 5.18: If \(f\) is a preflow, then there exists a path in \(G^f\) from every overflowing vertex \(x\) to \(s\).

Proof: Let \(W\) be the set of vertices other than \(t\) reachable from \(x\) in \(G^f\) and assume for the sake of contradiction that \(s \notin W\). Since \(e_y \ge 0\) for all \(y \in W\) and \(e_x > 0\), we have

\begin{align} 0 &< \sum_{y \in W} e_z\\ &= \sum_{y \in W} \sum_{z \in V} \bigl(f_{z,y} - f_{y,z}\bigr)\\ &= \sum_{y \in W} \sum_{z \in W} \bigl(f_{z,y} - f_{y,z}\bigr) + \sum_{y \in W} \sum_{z \notin W} \bigl(f_{z,y} - f_{y,z}\bigr)\tag{5.9}\\ &= \sum_{y \in W} \sum_{z \notin W} \bigl(f_{z,y} - f_{y,z}\bigr)\tag{5.10}\\ &\le \sum_{y \in W} \sum_{z \notin W} f_{z,y}.\tag{5.11} \end{align}

(5.10) follows from (5.9) because the first sum in (5.9) counts every edge between vertices in \(W\) twice, once with positive sign and once with negative sign, so this sum is zero. (5.11) follows from (5.10) because \(f_{y,z} \ge 0\) for every edge \((y,z)\).

Now \(0 < \sum_{y \in W} \sum_{z \notin W} f_{z,y}\) implies that there exists an edge \((z, y)\) with \(z \notin W\), \(y \in W\), and \(f_{z,y} > 0\). Thus, \(G^f\) contains the edge \((y, z)\), a contradiction because \(y \in W\) and \(z \notin W\). ▨

Corollary 5.19: Every vertex \(x \in V \setminus \{ s, t \}\) satisfies \(h_x \le 2n - 1\).

Proof: Initially, every vertex \(x \in V \setminus \{ s, t \}\) satisfies \(h_x = 0\). The height of \(x\) changes only as a result of relabelling \(x\), which happens only when \(e_x > 0\). By Lemma 5.18, there exists a path \(P = \langle x = x_0, \ldots, x_k = s \rangle\) from \(x\) to \(s\) in \(G^f\) at this time. By Observations 5.11 and 5.14, \(h\) is a valid height function at all times. Thus, immediately after relabelling \(x\), we have \(h_{x_{i-1}} \le h_{x_i} + 1\) for all \(1 \le i \le k\). Since \(h_{x_k} = h_s = n\) and \(k \le n - 1\), this shows that \(h_x = h_{x_0} \le h_s + n - 1 = 2n - 1\). ▨

Corollary 5.19 provides the tool to bound the number of Relabel operations and the number of saturating Push operations the algorithm performs.

Lemma 5.20: The generic preflow-push algorithm performs at most \(2n(n-1)\) Relabel operations.

Proof: For every vertex \(x \in V \setminus \{ s, t \}\), \(h_x = 0\) initially and \(h_x \le 2n - 1\) at all times. By Observation 5.13, \(h_x\) increases every time \(x\) is relabelled. Thus, \(x\) is relabelled at most \(2n - 1\) times. By summing over all vertices in \(V \setminus \{ s, t \}\) (\(s\) and \(t\) are never relabelled), we obtain a bound of \((2n - 1)(n - 2) \le 2n(n-1)\) on the number of Relabel operations. ▨

Lemma 5.21: The generic preflow-push algorithm performs at most \(2nm\) saturating Push operations.

Proof: It suffices to prove that every edge \((x, y)\) is used for at most \(2n\) saturating Push operations, counting both Push operations from \(x\) to \(y\) and from \(y\) to \(x\). Since there are \(m\) edges, this shows that the total number of saturating Push operations is at most \(2nm\).

Consider a saturating Push operation from \(x\) to \(y\) and let \(\ell\) be the height of \(x\) at the time of this Push operation. Since the Push operation is saturating, we have \(u^f_{x,y} = 0\) after this Push operation. In order to push more flow from \(x\) to \(y\) after this Push operation, we need to increase \(u^f_{x,y}\) so it becomes positive again, which is possible only by pushing flow from \(y\) to \(x\).

At the time we push flow from \(y\) to \(x\), we must have \(\ell' = h_y = h_x + 1 \ge \ell + 1\), where the last inequality holds because, by Observation 5.13, vertex heights do not decrease over the course of the algorithm.

At the time of the next Push operation from \(x\) to \(y\), we must have \(h_x = h_y + 1 \ge \ell' + 1 \ge \ell + 2\), by the same argument. Thus, between any two saturating Push operations from \(x\) to \(y\), \(h_x\) increases by at least two.

Since \(h_x = 0\) initially and \(h_x \le 2n - 1\) at all times, this shows that we perform at most \(n\) saturating Push operations from \(x\) to \(y\). By an analogous argument, the number of saturating Push operations from \(y\) to \(x\) is also bounded by \(n\). Thus, at most \(2n\) saturating Push operations use the edge \((x, y)\), as claimed. ▨

The most difficult part of the analysis is bounding the number of non-saturating Push operations because an edge can be used for several non-saturating Push operations in the same direction without relabelling the endpoints.

Lemma 5.22: The generic preflow-push algorithm performs at most \(8n^2m\) non-saturating Push operations.

Proof: To prove this, we define a potential function

\[\Phi = \sum_{e_x > 0} h_x.\]

Initially, \(\Phi = 0\) because every vertex other than \(s\) has height zero and \(e_s = 0\). Moreover, since every vertex has a non-negative height, \(\Phi\) is never negative.

The proof idea now is to bound the increase in potential resulting from every Relabel and saturating Push operation and to show that every non-saturating Push operation decreases the potential by at least one. Specifically, we show that Relabel and saturating Push operations do not add more than \(8n^2m\) in total to the potential. Since every non-saturating Push operation decreases the potential by at least one and the potential is never negative, this shows that there are at most \(8n^2m\) non-saturating Push operations.

Relabel operations: A Relabel operation does not change the excess of any vertex and changes the height of a single vertex. Since \(h_x \ge 0\) before the Relabel operation and \(h_x \le 2n - 1\) after the Relabel operation, this increases \(\Phi\) by at most \(2n - 1\).

Saturating Push operations: A saturating Push operation along an edge \((x, y)\) does not alter the height of any vertex, may or may not reduce \(x\)'s excess to \(0\), and results in \(y\) having positive excess after the Push operation. Thus, the greatest increase in potential is achieved if \(e_x > 0\) before and after the Push operation—so \(x\)'s contribution to \(\Phi\) does not change—and \(e_y = 0\) before the Push operation and \(e_y > 0\) after the Push operation—so \(y\)'s contribution to \(\Phi\) increases by \(h_y\). Since \(h_y \le 2n - 1\), this shows that a saturating Push operation increases \(\Phi\) by at most \(2n - 1\).

Total increase in potential: By Lemmas 5.20 and 5.21, the total number of Relabel and saturating Push operations is at most \(2n(n-1) + 2nm \le 4nm\) because we can assume that \(G\) is connected and, hence, \(m \ge n - 1\). As just observed, each such operation increases \(\Phi\) by at most \(2n - 1\). Thus, the total increase in potential due to Relabel and saturating Push operations is less than \(8n^2 m\).

Non-saturating Push operations: A non-saturating Push operation along an edge \((x, y)\) does not alter the height of any vertex, decreases \(e_x\) from \(e_x > 0\) to \(e_x = 0\) and may change \(e_y\) from \(e_y = 0\) to \(e_y > 0\). Thus, the decrease in potential is at least \(h_x - h_y\).

Since we push flow from \((x, y)\), we have \(h_x = h_y + 1\) at the time of the Push operation. Thus, \(\Phi\) decreases by at least one.

Since Relabel and saturating Push operations increase the potential by at most \(8n^2 m\) and every non-saturating Push operation decreases the potential by at least one, we obtain a bound of \(8n^2 m\) on the total number of non-saturating Push operations. ▨

Theorem 5.23: The generic preflow-push algorithm runs in \(O\bigl(n^2m\bigr)\) time.

Proof: By Lemmas 5.20, 5.21, and 5.22, the preflow-push algorithm performs \(O\bigl(n^2\bigr)\) Relabel and \(O\bigl(n^2m\bigr)\) Push operations. The following exercise asks you to show how to implement every Relabel operation in \(O(n)\) time and every Push operation in constant time, and to show how to implement a data structure that can be used to pick the next vertex to be relabelled or the next edge along which to push flow in constant time. Thus, the total cost of the algorithm is \(O\bigl(n^2 \cdot n + n^2m\bigr) = O\bigl(n^2m\bigr)\). ▨

Exercise 5.2:

• Prove that every Relabel operation can be implemented in \(O(n)\) time and that every Push operation can be implemented in \(O(1)\) time.

• Provide a data structure that supports a NextOp operation, which returns either an edge \((x, y)\) that can be used for a Push operation (i.e., \(e_x > 0\), \(u^f_{x,y} > 0\), and \(h_x = h_y + 1\)) or a vertex \(x\) with \(e_x > 0\) to be relabelled if no such edge \((x, y)\) exists.

  • This NextOp operation should take constant time.
  • Updating the data structure after a Relabel operation should take \(O(n)\) time.
  • Updating it after a Push operation should take constant time.