5.2.1.1. Correctness of the Generic Preflow-Push Algorithm

The next lemma will be crucial for showing that the preflow-push algorithm does indeed compute a maximum flow.

Lemma 5.16: At any point during the course of the preflow-push algorithm, there is no path from \(s\) to \(t\) in the residual network \(G^f\).

Proof: Assume for the sake of contradiction that the residual network \(G^f\) does contain a path \(P = \langle s=x_0, \ldots, x_k=t \rangle\) from \(s\) to \(t\) at some point during the course of the algorithm. We can assume w.l.o.g. that \(P\) is a simple path, that is, that it visits every vertex at most once. Thus, it has \(k \le n-1\) edges. By Observations 5.11 and 5.14, \(h\) is a valid height function at all times. Thus, \(P\) satisfies \[h_{x_{i-1}} \le h_{x_i} + 1 \quad \forall1 \le i \le k.\]

In particular,

\[n = h_s \le h_t + k \le h_t + n - 1 = n - 1,\]

a contradiction. ▨

The following theorem now establishes the correctness of the preflow-push algorithm under the assumption that the algorithm terminates:

Theorem 5.17: If the generic preflow-push algorithm terminates, then the edge labelling \(f\) it returns is a maximum \(st\)-flow.

Proof: At any point during the algorithm's execution, \(f\) is a valid preflow, that is, it satisfies all capacity constraints. Once the algorithm terminates, \(f\) also satisfies flow conservation. Thus, \(f\) is a feasible \(st\)-flow.

By Lemma 5.16, there is no path from \(s\) to \(t\) in \(G^f\). As shown in the proof of Theorem 5.4, this implies that \(f_s\) equals the capacity of some \(st\)-cut in \(G\) and is thus a maximum \(st\)-flow. ▨