Proofs: Cost scaling min-cost flow algorithm

Cost scaling returns a maximum flow of least cost full

This proof shows: correctness, termination.

Let $N$ have integer capacities $c \ge 0$ and integer costs $w$. Self-loops are set aside at the start: a self-loop is full if its cost is negative and empty otherwise, which is optimal for it alone, and since a self-loop does not change any balance, this choice is independent of the rest. All arcs below are arcs of edges that are not self-loops. Costs are multiplied by $n + 1$; we write $w$ for the scaled costs. For potentials $p$, the reduced cost of a residual arc $x = (v, u)$ is $c_p(x) = w(x) + p(v) - p(u)$, and $w(\bar x) = -w(x)$ for the reverse arc $\bar x$. A pseudoflow is $\varepsilon$-optimal for $p$ if every residual arc has $c_p \ge -\varepsilon$.

Line L1. Edmonds-Karp returns a maximum s-t flow $f^*$ of value $F$; see the page on Edmonds-Karp. From then on, for a pseudoflow $f$ let $e_f(v)$ be the net flow into $v$ under $f$ minus that under the flow at the start of the current refine. Every push moves an amount from the excess of one vertex to another, so the sum of excesses is 0.

Invariant. At the start of each refine, $f$ satisfies the capacity bounds, conserves flow at every vertex other than $s$, $t$, has value $F$, and is $2\varepsilon$-optimal for the current $p$, where $\varepsilon$ is the value set by line L4. Before the first refine, $p = 0$ and every residual arc has $c_p(x) = w(x) \ge -\max|w|$, and the first $\varepsilon = \lceil \max|w| / 2 \rceil$ satisfies $2\varepsilon \ge \max|w|$. Later refines start from the result of the previous refine with $\varepsilon_{\text{old}}$, which is $\varepsilon_{\text{old}}$-optimal by Claim 1 below, and $2 \lceil \varepsilon_{\text{old}}/2 \rceil \ge \varepsilon_{\text{old}}$.

Claim 1 ($\varepsilon$-optimality is kept within refine). After line L5, every residual arc has $c_p \ge 0$: an arc with $c_p < 0$ was saturated and left the residual graph, and its reverse has $c_p > 0$. A push in line L8 is along an admissible arc $x$, $c_p(x) < 0$; it may add $\bar x$ to the residual graph, with $c_p(\bar x) = -c_p(x) > 0$. A relabel in line L9 happens when $v$ has no admissible arc, so every residual arc $x = (v, u)$ has $c_p(x) \ge 0$, that is $p(v) \ge p(u) - w(x)$. The new value $p'(v) = \max_x (p(u) - w(x)) - \varepsilon$ gives every residual arc out of $v$ a reduced cost at least $-\varepsilon$, with equality for the maximizer, and $p'(v) \le p(v) - \varepsilon$. Lowering $p(v)$ raises the reduced costs of arcs into $v$. The maximum exists: see Claim 2. So the pseudoflow stays $\varepsilon$-optimal.

Claim 2 (paths to a deficit). Let $f_0$ be the flow at the start of the refine and $f$ the current pseudoflow. If $e_f(v) > 0$, there is a vertex $u$ with $e_f(u) < 0$ and a path from $v$ to $u$ in $G_f$ whose reversed path lies in $G_{f_0}$. Proof. Let $g = f_0 - f$ as a function on edges. Where $g(e) > 0$, the forward arc of $e$ is residual for $f$ (as $f(e) < f_0(e) \le c(e)$) and the backward arc is residual for $f_0$; where $g(e) < 0$, the backward arc of $e$ is residual for $f$ and the forward arc for $f_0$. Orient each edge with $g(e) \ne 0$ in the direction in which $g$ is positive, as an arc of $G_f$. The net outflow of $g$ at each vertex $x$ is $e_f(x)$. Decompose $g$ into paths and cycles: a path starts at a vertex of positive $e_f$ and ends at one of negative $e_f$. Since $e_f(v) > 0$, some path starts at $v$. $\square$ In particular an active vertex has a residual arc, so the maximum in line L9 is over a nonempty set.

Claim 3 (relabel bound). During a refine with $\varepsilon$, each potential drops by at most $3(n - 1)\varepsilon$ in total. Proof. A vertex is relabeled only while active, and a vertex never pushes more than its excess, so a vertex with $e_f(u) < 0$ was never active in this refine and still has its potential $p_0(u)$ from the start. For the path $P$ of Claim 2 from $v$ to such a $u$, $\varepsilon$-optimality gives $w(P) + p(v) - p(u) \ge -(n - 1)\varepsilon$, and $2\varepsilon$-optimality of $f_0$ for $p_0$ along the reversed path gives $-w(P) + p_0(u) - p_0(v) \ge -2(n - 1)\varepsilon$. Adding, with $p(u) = p_0(u)$: $p_0(v) - p(v) \le 3(n - 1)\varepsilon$. $\square$

Termination of refine. By Claim 1 each relabel lowers $p(v)$ by at least $\varepsilon$, so by Claim 3 each vertex is relabeled at most $3(n - 1)$ times. Between two relabels of $v$, an arc $x$ out of $v$ that a push saturates becomes residual again only after a push along $\bar x$, which needs $c_p(\bar x) < 0$, so $u$ must be relabeled in between; this bounds saturating pushes by $O(nm)$. The admissible graph stays acyclic: after line L5 it is empty, a push adds no admissible arc, and a relabel of $v$ makes every arc into $v$ have $c_p \ge 0$, so it creates no cycle through $v$. Let $\Phi$ be the sum, over active vertices $x$, of the number of vertices reachable from $x$ in the admissible graph. A non-saturating push along $(v, u)$ makes $v$ inactive and may make $u$ active, and $u$ reaches fewer vertices than $v$ by acyclicity, so $\Phi$ drops by at least 1. Relabels and saturating pushes raise $\Phi$ by at most $n$ each, so there are $O(n \cdot n^2 + n \cdot nm) = O(n^2 m)$ non-saturating pushes. So line L6 stops after finitely many steps, with no active vertex. Since excesses sum to 0 and none is positive, all are 0.

After refine. All excesses are 0, so $f$ has the same net flow at every vertex as $f_0$: it conserves flow at every vertex other than $s$, $t$ and has value $F$. Every push respects residual capacities, so $0 \le f \le c$. By Claim 1, $f$ is $\varepsilon$-optimal, which is $2\varepsilon'$-optimal for the next $\varepsilon' = \lceil \varepsilon / 2 \rceil$. So the invariant holds at the next refine.

Termination of the outer loop. While $\varepsilon > 1$, $\lceil \varepsilon / 2 \rceil < \varepsilon$, so $\varepsilon$ reaches 1 after finitely many refines, and line L10 stops after the refine with $\varepsilon = 1$.

Optimality. At the end $f$ is a maximum flow and 1-optimal for the scaled costs. Let $Z$ be a cycle of $G_f$ with $k \le n$ arcs. The potentials cancel around a cycle, so its scaled cost is $\sum_{x \in Z} c_p(x) \ge -k \ge -n$. Its scaled cost is $n + 1$ times its original cost, an integer, so the original cost is at least $-n/(n + 1) > -1$, hence at least 0. So $G_f$ has no negative cycle. Any other maximum flow $g$ differs from $f$ by a circulation $g - f$ in $G_f$, which splits into cycles of $G_f$, each of nonnegative cost; so $g$ costs at least as much as $f$. With the self-loops set as above, $f$ is a maximum flow of least cost. $\blacksquare$