Proofs: Capacity scaling max-flow algorithm

Capacity scaling makes at most 2m augmentations per phase full

This proof shows: time.worst.

Use the notation of the correctness proof, let $F$ be the maximum flow value, and assume $m \ge n - 1$ (otherwise add $O(n)$ per search).

Lemma 1. At the end of a $\Delta$-phase, $F - |f| < m \Delta$.

Proof. Let $S$ be the set of vertices reachable from $s$ in $G_f(\Delta)$; $t \notin S$ because the phase has ended. For every s-t flow $g$, $|g| - |f| \le \sum (c(e) - f(e)) + \sum f(e)$, where the first sum is over edges from $S$ to $\bar S$ and the second over edges from $\bar S$ to $S$, since $|g| = g(S, \bar S) - g(\bar S, S) \le c(S, \bar S)$ and $|f| = f(S, \bar S) - f(\bar S, S)$. An edge $e$ from $S$ to $\bar S$ has $c(e) - f(e) = c_f(e^+) < \Delta$, else its head would be reachable in $G_f(\Delta)$; an edge from $\bar S$ to $S$ has $f(e) = c_f(e^-) < \Delta$ for the same reason. Each edge is in at most one of the two sums, so $|g| - |f| < m\Delta$ when some edge crosses the cut, and $|g| - |f| \le 0$ otherwise. Take $g$ maximum. $\square$

Lemma 2. Each phase performs fewer than $2m$ augmentations, or none.

Proof. The first threshold $\Delta_0$ is a power of 2, and line L7 halves it, so every threshold is a power of 2 and each later threshold $\Delta$ follows a phase with threshold exactly $2\Delta$. For the first phase, $\Delta_0 \le U < 2\Delta_0$ by the choice in line L2, so $F \le c(\{s\}, V \setminus \{s\}) \le mU < 2m\Delta_0$. For a later phase with threshold $\Delta$, Lemma 1 for the previous phase says that the missing value at the start is less than $2m\Delta$. In every phase each augmentation carries at least $\Delta$, so the phase has fewer than $2m\Delta / \Delta = 2m$ augmentations. $\square$

Theorem. The algorithm runs in $O(m^2 \log U)$ time and $\Theta(n + m)$ space.

Proof. There are $\lfloor \log_2 U \rfloor + 1$ phases. Each phase has fewer than $2m$ augmentations, each preceded by one search, plus one failing search; a search costs $O(n + m) = O(m)$ and an augmentation $O(n)$. So a phase costs $O(m^2)$ and the total is $O(m^2 \log U)$, plus $O(m)$ for lines L1, L2, L8 and L9. The arrays of residual capacities, the adjacency lists, the queue and the parent arcs take $\Theta(n + m)$ space. $\blacksquare$

Capacity scaling returns a maximum flow and a minimum cut full

This proof shows: correctness, termination.

Let $N = (G, c, s, t)$ be a flow network with integer capacities $c(e) \ge 0$, $m$ edges and $s \ne t$, and $U = \max_e c(e)$. Write $c_f$ for the residual capacities, $f(e) = c_f(e^-)$, $G_f$ for the residual graph of arcs with $c_f > 0$, and $G_f(\Delta)$ for the arcs with $c_f \ge \Delta$.

Claim 1 (invariant). Before and after each augmentation, $f$ is an s-t flow, every $c_f$ is a nonnegative integer, and $c_f(e^+) + c_f(e^-) = c(e)$ for each edge.

Proof. True after line L1. Line L4 finds a path $P$ of $G_f(\Delta) \subseteq G_f$ from $s$ to $t$; BFS marks each vertex once, so $P$ is simple. Line L5 sets $\delta$ to the least $c_f$ on $P$, an integer with $\delta \ge \Delta \ge 1$. Line L6 is an augmentation along $P$ by its bottleneck, which keeps the invariant by the augmentation lemma of augmenting path, and raises $|f|$ by $\delta$. $\square$

Claim 2 (termination). Each augmentation raises $|f|$ by at least 1, and $|f| \le c(\{s\}, V \setminus \{s\})$, so there are finitely many augmentations. Line L7 halves $\Delta$, so the loop of line L3 runs $\lfloor \log_2 U \rfloor + 1$ times, or not at all if $U = 0$.

Claim 3 (no augmenting path at the end). If $U \ge 1$, the last phase has $\Delta = 1$ and ends when BFS over the arcs with $c_f \ge 1$ does not reach $t$. Since all $c_f$ are integers, $c_f \ge 1$ means $c_f > 0$, so $t$ is not reachable in $G_f$. If $U = 0$, $G_f$ has no arcs at all.

Claim 4 (optimality). Line L8 computes the set $S$ of vertices reachable from $s$ in $G_f$, with $s \in S$ and, by Claim 3, $t \notin S$. Each edge $e = (u, v)$ with $u \in S$, $v \notin S$ has $c_f(e^+) = 0$, so $f(e) = c(e)$; each edge $(v, u)$ with $v \notin S$, $u \in S$ has $c_f(e^-) = 0$, so $f(e) = 0$. By conservation, $|f| = f(S, \bar S) - f(\bar S, S) = c(S, \bar S)$. Every s-t flow has value at most $c(S, \bar S)$ and every s-t cut has capacity at least $|f|$, so the flow is maximum and the cut is minimum. $\blacksquare$