Proofs: Dinic's algorithm

Dinic's algorithm runs in O(n^2 m) time full

This proof shows: time.worst.

Fix a run on a network with $n$ vertices and $m$ edges, and assume, as for every maximum flow bound stated in terms of $m$, that $m \ge n - 1$ after removing the vertices that no edge touches; otherwise add $O(n)$ to each bound. Each arithmetic operation and comparison costs $O(1)$.

Theorem 1 (phases). There are at most $n$ runs of line L3. By Claim 5 of the correctness proof, $d_f(t)$ grows by at least 1 in each phase, and it lies in $\{1, \dots, n - 1\}$ while the loop continues, so there are at most $n - 1$ phases and one final search.

Theorem 2 (one phase costs O(nm)). Line L1 costs $O(m)$ once. Line L3 is a breadth-first search over at most $2m$ arcs: $O(n + m)$. Line L5 costs $O(n)$. In the loop of lines L7 to L14:

• lines L12 and L14 each move a pointer one arc forward, and there are $2m$ arcs, so they run at most $2m$ times in all, at $O(1)$ each;
• line L9 runs at most $m$ times (Claim 4 of the correctness proof) and costs $O(|P|) = O(n)$ each time, since $|P| = d(t) \le n - 1$;
• line L11 adds an arc to $P$, and each arc added to $P$ leaves it later by line L9 (at most $n - 1$ arcs per run, already counted) or by line L14 (one arc per run). So line L11 runs at most $(n - 1) \cdot m + 2m$ times;
• line L13 runs once.

So the loop costs $O(nm + m) = O(nm)$, and one phase costs $O(n + m + nm) = O(nm)$.

Theorem 3 (total). By Theorems 1 and 2 the time is $O(n \cdot nm) = O(n^2 m)$. The arrays $c_f$, the adjacency lists, $\text{level}$, $it$, the queue and $P$ take $\Theta(n + m)$ space. Nothing in the count uses integrality, so the bound holds for real capacities. $\blacksquare$

Dinic's algorithm 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 real capacities $c(e) \ge 0$ and $s \ne t$. 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 $d(v)$ for the value $\text{level}[v]$ computed in line L3 of the current phase. The level graph $L_f$ is the set of arcs $(v, w)$ with $c_f > 0$ and $d(w) = d(v) + 1$; its arcs are tested with the residual capacities of the moment.

Claim 1 (each augmentation keeps a flow). When line L9 runs, $P$ is a walk from $s$ to $u = t$ built by line L11, so each arc of $P$ had $c_f > 0$ and goes up one level. The levels along $P$ are $0, 1, \dots, d(t)$, so $P$ is a simple path. Every arc of $P$ still has $c_f > 0$ at line L9: an arc of $L_f$ loses residual capacity only through an augmentation, and an augmentation restarts the walk with $P$ empty. So $\Delta > 0$, and by the invariant proved for Ford-Fulkerson (residual capacities stay nonnegative, $c_f(e^+) + c_f(e^-) = c(e)$, conservation holds) $f$ stays an s-t flow and its value grows by $\Delta$.

Claim 2 (level arcs only shrink in a phase). An augmentation adds residual capacity only to reverses $(w, v)$ of arcs $(v, w)$ of $L_f$, which have $d(v) = d(w) - 1$, so they are not level arcs. The levels $d$ are fixed during the phase. Hence the set of arcs of $L_f$ with $c_f > 0$ only loses members during the phase.

Claim 3 (dead vertices are dead). Call $u$ dead when $it[u]$ has run past the last arc of $u$. Invariant: no dead vertex has a path to $t$ in $L_f$ using arcs with $c_f > 0$, and every arc that a pointer has passed is either not a level arc, or has $c_f = 0$, or ends at a dead vertex. A pointer moves in line L12 only when the arc fails the test of line L10, that is, it is not a level arc or it has $c_f = 0$; by Claim 2 it stays so. A pointer moves in line L14 past the arc $(v, u)$ just after $u$ was found dead. Every arc of a dead $u$ has been passed, so each one is useless or ends at a dead vertex, and by induction on the order in which vertices die, $u$ has no path to $t$ with positive level arcs. The sink $t$ never dies, because line L8 runs before lines L10 to L14 whenever $u = t$.

Claim 4 (each phase ends and finds a blocking flow). Each pass of the loop runs one of lines L9, L11, L12, L14. Lines L12 and L14 move a pointer, at most $2m$ times in all. Line L9 makes some arc of $P$ have $c_f = 0$, and by Claim 2 it stays so, so it is in no later $P$; $L_f$ has at most $m$ arcs, since the two arcs of one edge cannot both go up a level, so line L9 runs at most $m$ times. Line L11 runs at most $d(t) \le n - 1$ times between two runs of lines L9 or L14, since each run raises the level of $u$ by 1. So the loop ends, and it ends only in line L13, with $s$ dead. By Claim 3, $L_f$ then has no s-t path with all $c_f > 0$: the flow added in this phase is a blocking flow of the level graph of the phase start.

Claim 5 (termination). By the lemma on blocking flows, adding a blocking flow of $L_f$ makes $d_f(t)$ strictly larger. While the loop of line L2 continues, $1 \le d_f(t) \le n - 1$. So there are at most $n - 1$ phases before line L4 leaves the loop.

Claim 6 (optimality). In the last run of line L3, $t$ is not reached, and $S = \{v : d(v) \ge 0\}$ is exactly the set of vertices reachable from $s$ in $G_f$, with $s \in S$ and $t \notin S$. Each edge $(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)$. Since every s-t flow $g$ has $|g| \le c(S, \bar S)$ and every s-t cut $X$ has $c(X, \bar X) \ge |f|$, the flow is maximum and the cut is minimum. $\blacksquare$