Negative cycle-canceling

Abstract view

Algorithmic problem: Min-cost flow problem

Type of algorithm: loop

Invariant:

1. The flow is feasible.
2. If all upper bounds are integral, the flow is integral as well.

Variant: The cost of the flow decreases.

Break condition: There is no more negative cycle in the residual network.

Induction basis

Abstract view: Start with an arbitrary feasible flow.

Implementation: The problem to find a feasible flow is reduced to a max-flow problem as follows:

1. Insert new vertices, [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].
2. For each original node [math]\displaystyle{ v\in V }[/math] such that [math]\displaystyle{ b[v]\gt 0 }[/math]: Insert an arc [math]\displaystyle{ (s,v) }[/math] with capacity [math]\displaystyle{ b[v] }[/math].
3. For each original node [math]\displaystyle{ v\in V }[/math] such that [math]\displaystyle{ b[v]\lt 0 }[/math]: Insert an arc [math]\displaystyle{ (v,t) }[/math] with capacity [math]\displaystyle{ -b[v] }[/math].
4. Determine a maximum flow from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] in the extended graph (cost factors and balance values are disregarded).
5. If all arcs [math]\displaystyle{ (s,v) }[/math] are saturated, return the restriction of this flow to the original arcs.
6. Otherwise, the original min-cost flow instance is infeasible.

Proof: If the arcs leaving [math]\displaystyle{ s }[/math] (or, equivalently, the arcs entering [math]\displaystyle{ t }[/math]) are saturated, the flow balances at all original nodes are obviously fulfilled in the original min-cost flow instance. On the other hand, if a feasible flow exists at all in the original min-cost flow instance, its extension to the inserted arcs yields a flow that saturates all arcs leaving [math]\displaystyle{ s }[/math]. Therefore, if the maximum flow in the extended flow network does not saturate all of these arcs, the original instance is infeasible.

Induction step

Abstract view:

1. Find a cycle of negative cost in the residual network.
2. Augment the flow along this cycle up to saturation.

Implementation of step 1:

1. Run an all-pairs shortest-paths algorithm on the residual network [math]\displaystyle{ (G_f,u_f) }[/math], where for each arc [math]\displaystyle{ (v,w)\in A }[/math], the length of [math]\displaystyle{ (v,w) }[/math] is [math]\displaystyle{ c(v,w) }[/math] in case [math]\displaystyle{ (v,w)\in A_f }[/math], and the length of [math]\displaystyle{ (w,v) }[/math] is [math]\displaystyle{ -c(v,w) }[/math] in case [math]\displaystyle{ (w,v)\in A_f }[/math]. Let the algorithm construct an arborescence or a negative cycle.
2. If the distance [math]\displaystyle{ v\rightarrow v }[/math] is 0 for all [math]\displaystyle{ v\in V }[/math], the break condition applies.
3. Otherwise (that is, the distances [math]\displaystyle{ v\rightarrow v }[/math] of some nodes [math]\displaystyle{ v\in V }[/math] are negative): Reconstruct one negative cycle [math]\displaystyle{ C }[/math].

Proof: The invariant and the variant are obviously fulfilled.

Correctness

In the following, arithmetic operations and comparisons of flows are arc-wise. For a generalized cycle [math]\displaystyle{ C }[/math] and [math]\displaystyle{ \varepsilon\gt 0 }[/math], adding [math]\displaystyle{ \varepsilon\cdot C }[/math] to a flow [math]\displaystyle{ f }[/math] means that [math]\displaystyle{ f }[/math] is augmented along [math]\displaystyle{ C }[/math] by [math]\displaystyle{ \varepsilon }[/math].

First we will show a general fact: For two feasible flows, [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math], there are generalized cycles [math]\displaystyle{ C_1,\ldots,C_k }[/math] in [math]\displaystyle{ G }[/math] and [math]\displaystyle{ \varepsilon_1,\ldots,\varepsilon_k\gt 0 }[/math] such that:

1. Decomposition of [math]\displaystyle{ f_2-f_1 }[/math]: It is [math]\displaystyle{ f_2=f_1+\varepsilon_1\cdot C_1+\cdots+\varepsilon_k\cdot C_k }[/math].
2. Consistency: For each arc [math]\displaystyle{ a\in A }[/math] and [math]\displaystyle{ i,j\in\{1,\ldots,k\} }[/math]: If [math]\displaystyle{ a }[/math] belongs to [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math], then [math]\displaystyle{ a }[/math] is a forward arc on both cycles, or [math]\displaystyle{ a }[/math] is a backward arc in both cycles.

To prove this general fact, we apply an induction on the number [math]\displaystyle{ d }[/math] of arcs on which [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math] differ. For [math]\displaystyle{ d=0 }[/math], it is [math]\displaystyle{ f_1=f_2 }[/math], so the empty set of cycles ([math]\displaystyle{ k=0 }[/math]) describes the difference between [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math].

So suppose [math]\displaystyle{ d\gt 0 }[/math]. Let [math]\displaystyle{ (v_1,v_2) }[/math] be an arc on which [math]\displaystyle{ f_1 }[/math] and [math]\displaystyle{ f_2 }[/math] differ, say [math]\displaystyle{ f_1(v_1,v_2)\lt f_2(v_1,v_2) }[/math]. Then there is either an arc [math]\displaystyle{ (v_2,v_3) }[/math] with [math]\displaystyle{ f_1(v_2,v_3)\lt f_2(v_2,v_3) }[/math] or an arc [math]\displaystyle{ (v_3,v_2) }[/math] with [math]\displaystyle{ f_1(v_3,v_2)\gt f_2(v_3,v_2) }[/math]. This argument may be continued, so we obtain a sequence [math]\displaystyle{ v_1,v_2,v_3,v_4,\ldots }[/math] such that for all [math]\displaystyle{ i=1,2,3,\ldots }[/math], there is [math]\displaystyle{ (v_i,v_{i+1}) }[/math] with [math]\displaystyle{ f_1(v_i,v_{i+1})\lt f_2(v_i,v_{i+1}) }[/math] or [math]\displaystyle{ (v_{i+1},v_i) }[/math] with [math]\displaystyle{ f_1(v_{i+1},v_i)\lt f_2(v_{i+1},v_i) }[/math]. Since the number of nodes is finite, there must be [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] such that [math]\displaystyle{ v_i=v_j }[/math]. Therefore, a generalized cycle [math]\displaystyle{ C_1 }[/math] is closed such that [math]\displaystyle{ f_1(a)\lt f_2(a)\leq u(a) }[/math] on each forward arc and [math]\displaystyle{ f_1(a)\gt f_2(a)\geq 0 }[/math] on each backward arc. In particular, there is [math]\displaystyle{ \varepsilon_1\gt 0 }[/math] such that [math]\displaystyle{ f_1+\varepsilon_1\cdot C_1 }[/math] is feasible. If [math]\displaystyle{ \varepsilon_1 }[/math] is chosen maximal, [math]\displaystyle{ f_1+\varepsilon_1\cdot C_1 }[/math] agrees one at least one more arc with [math]\displaystyle{ f_2 }[/math] than [math]\displaystyle{ f_1 }[/math]. Now the induction hypothesis proves the general fact.

Finally, we are in a position to prove correctness of the algorithm. For that, we have to show that a feasible flow is minimum if it admits no negative cycle. So assume a feasible flow [math]\displaystyle{ f }[/math] is not minimum. Then there is a feasible flow [math]\displaystyle{ \tilde{f} }[/math] such that [math]\displaystyle{ c(\tilde{f})\lt c(f) }[/math]. There are [math]\displaystyle{ C_1,\ldots,C_k }[/math] and [math]\displaystyle{ \varepsilon_1,\ldots,\varepsilon_k }[/math] as described above. Since [math]\displaystyle{ c(\tilde{f})\lt c(f) }[/math], at least one of the cycles must be a negative one,say [math]\displaystyle{ C_i }[/math]. Since the cycles are consistent, they may be permuted in the decomposition, so [math]\displaystyle{ f+\varepsilon_i\cdot C_i }[/math] is feasible.

Complexity

Statement: If all upper bounds are integral, the asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(T\cdot C\cdot U) }[/math], where [math]\displaystyle{ T }[/math] is the asymptotic complexity of the all-pairs shortest-paths problem, [math]\displaystyle{ C=\sum_{a\in A}|c(a)| }[/math], and [math]\displaystyle{ U=\max\{u(a)|a\in A\} }[/math].

Proof: The initial flow has a total cost of at most [math]\displaystyle{ C\cdot U }[/math], and the min-cost flow has a total cost of at least [math]\displaystyle{ -C\cdot U }[/math]. Therefore, the number of iterations is in [math]\displaystyle{ \mathcal{O}(C\cdot U) }[/math]. The complexity of an iteration is dominated by the all-pairs shortest-paths algorithm.