Proofs: Almost-linear-time maximum flow algorithm

The exact version of the almost-linear max flow method returns a maximum flow full

This proof shows: correctness, termination.

This proof is for the version on the algorithm page, with exact min-ratio cycles and the finish of lines L7 to L9. The step bound of the real algorithm is proved by Chen and others and is not repeated here.

Setup. Variables are the original edges with $u_e > 0$ and $u \ne v$ (lower bound 0, upper bound $u_e$, cost 0), the return edge $(t, s)$ with upper bound $U_s$ and cost $-1$, and the edges at $z$ with upper bound $2|b(v)|$ and cost 4. All upper bounds are integers: $b(v)$ is a sum of halves of integers, so $2|b(v)|$ is an integer. Write $x$ for the vector of variable values, and call $x$ a circulation if inflow equals outflow at every vertex, including $z$.

Claim 1 (start). After line L2, $x$ is a circulation and $0 < x_e < \bar u_e$ for every variable. Proof. After line L1 each variable is at half its bound, and $b(v)$ is the inflow minus outflow at $v$. The edge $v \to z$ with value $b(v) > 0$, or $z \to v$ with value $-b(v)$ for $b(v) < 0$, cancels it. At $z$ the inflow minus outflow is $\sum_v b(v) = 0$, as every variable adds to one head and subtracts from one tail. Every value is half of its bound, which is positive. $\square$

Claim 2 (steps). Every step of line L6 keeps a strictly interior circulation. Proof. $\Delta$ is a cycle, so adding any multiple keeps the circulation. The room $\rho$ is the least distance to a bound along $\Delta$, and the step is at most $\rho / 2$, so every value stays strictly inside. $\square$

Claim 3 (the loop ends). Line L3 allows a fixed number of steps, and line L5 is a finite procedure: each Dinkelbach round finds a cycle with a strictly lower ratio, and a graph has finitely many simple cycles. Line L6 tries finitely many $\eta$. $\square$

Claim 4 (rounding). Line L7 ends with an integral circulation within the bounds whose cost is at most the cost of $x$. Proof. Call a variable fractional if its value is not an integer. Suppose some variable at vertex $v$ is fractional. The net flow at $v$ is 0, an integer, and the integral variables contribute an integer, so the fractional ones at $v$ sum (with signs) to an integer, which is impossible with only one of them. So in the multigraph of fractional variables every vertex with an edge has degree at least 2, and it contains a cycle $Q$. Pushing $\delta$ around $Q$ in one direction keeps the circulation and changes the cost by $\delta$ times the signed cost of $Q$; line L7 picks the direction where this is at most 0. It takes $\delta$ as the least distance to the next integer in the direction of motion, so each value stays between two consecutive integers it lay between, hence within its integer bounds, and at least one variable becomes integral. Integral variables are not in $Q$, so they stay integral, and there are finitely many variables, so line L7 ends. $\square$

Claim 5 (removing $z$). Line L8 ends with value 0 on all edges at $z$, an integral circulation within bounds, and a cost not higher. Proof. If an edge out of $z$ has positive value, let $R$ be the set of vertices reachable from $z$ by edges of positive value. If no edge of positive value entered $z$ from $R$, then the set $R \setminus \{z\}$ would receive positive flow from $z$ and, since all edges of positive value leaving it stay in $R$, send none to $z$; the total inflow minus outflow over $R \setminus \{z\}$ would be positive, which contradicts conservation. So the search finds a cycle through $z$ of positive values. Subtracting its least value keeps an integral circulation within bounds and sets one value to 0; the cost changes by minus the cost of the cycle, which uses two edges at $z$ (cost 8) and at most one return edge (cost $-1$), so it falls. Each round makes one more value 0 and never raises one, so line L8 ends. If no edge leaves $z$ with positive value, conservation at $z$ shows that none enters it either. $\square$

Claim 6 (output). After line L8, the values on the original edges form an integral s-t flow $f$ within capacities. Conservation holds at every vertex other than $s$ and $t$, since the only other variables there, edges at $z$, are 0, and the return edge touches only $s$ and $t$. Dropped edges (capacity 0 and self-loops) get flow 0, which is feasible. Line L9 runs Ford-Fulkerson with breadth-first paths from $f$; each augmentation raises the integer value by at least 1 and the value is at most $U_s$, so it ends, and when no augmenting path is left the set reachable from $s$ in the residual graph is a cut whose capacity equals the flow value, so $f$ is a maximum flow. $\square$

Claim 7 (when the interior phase suffices). Let $F^*$ be the least cost of a circulation of the extended instance. Integral circulations of the original edges plus the return edge with cost $-F$ are s-t flows of value $F$, so $F^* \le -F_{\max}$; and any circulation decomposes into cycles, those through $z$ cost at least $8 - 1 > 0$, so $F^* = -F_{\max}$, an integer. If the interior phase ends with $c^\top x < F^* + 1$, the rounded circulation of Claim 4 is integral, its cost is an integer at least $F^*$ and less than $F^* + 1$, so it equals $F^*$. An optimal circulation with positive value at $z$ could drop a cycle through $z$ and lower the cost, by Claim 5, so its values at $z$ are 0 and line L8 does nothing. Its return edge carries $F_{\max}$, so line L9 finds no augmenting path. $\square$

By Claims 1 to 6 the algorithm ends and returns an integral maximum flow. $\blacksquare$