6.4.2. Cancelling Negative Cycles

As already said, the second phase of the negative cycle cancelling algorithm starts with the feasible flow computed in the first phase and reduces its cost by cancelling negative cycles.

Let \(f\) be the current flow. If there is no negative cycle in its residual network \(G^f\), then \(f\) is a minimum-cost flow and we return it. Otherwise, let \(C\) be a negative cycle in \(G^f\) and let

\[\delta = \min_{e \in C} u^f_e\]

be the minimum residual capacity of the edges in \(C\). Then we construct a new flow \(f'\) defined as

\[f'_{x,y} = \begin{cases} f_{x,y} + \delta & \text{if } (x, x) \in C\\ f_{x,y} - \delta & \text{if } (y, x) \in C\\ f_{x,y} & \text{otherwise.} \end{cases}\]

By Lemma 6.7, \(f'\) is indeed a flow. We replace \(f\) with \(f'\) and start another iteration. This process continues until \(G^f\) contains no negative cycle and the algorithm returns \(f\). By Lemma 6.3, \(f\) is a minimum-cost flow at this point. The three questions we need to answer are whether the algorithm terminates, how many iterations it takes to do so, and how long every iteration takes.

We focus on the last question first. Given a negative cycle \(C\) in \(G^f\), we can easily find \(\delta\) in \(O(n)\) time by inspecting every edge in \(C\), and we can compute \(f'\) from \(f\) in \(O(n)\) time by adjusting the flow along every edge of \(G\) that corresponds to an edge in \(C\). The only challenge therefore is to find \(C\) (or determine that no such cycle exists). By the following lemma, this takes \(O(nm)\) time.

Lemma 6.16: It takes \(O(nm)\) time to decide whether a network \(G\) has a negative cycle and, if so, find one.

Proof: Recall the Bellman-Ford algorithm for computing shortest paths from a vertex \(s\) to all vertices in \(G\) in the absence of negative cycles. This algorithm takes \(O(nm)\) time. It turns out that we can use the same algorithm, with minor modifications, also to detect and find negative cycles.

The Bellman-Ford algorithm initializes distance labels \(d_x\) for all vertices \(x \in G\) by setting \(d_s = 0\) and \(d_x = \infty\). It also maintains the predecessor \(p_x\) of every vertex \(x\) on the shortest path from \(s\) to \(x\) found so far. Initially, \(p_x = \textrm{NULL}\). Then the algorithm repeats the following steps \(n - 1\) times, that is, it runs for \(n - 1\) iterations:

• For every vertex \(y \in G\), set

  \[d'_y = \min\bigl(d_y, \min_{(x,y) \in G} \bigl(d_x + w_{x,y}\bigr)\bigr),\]

  where \(w_{x,y}\) is the length of the edge \((x,y)\).

• If \(d'_y < d_y\), then set \(p_y = x\), where \(x\) is any in-neighbour of \(y\) that satisfies \(d'_y = d_x + w_{x,y}\).

• Finally, set \(d_y = d'_y\) for all \(y \in G\).

In the remainder of this proof, we use \(d^{(0)}_x\) and \(p^{(0)}_x\) to refer to the initial values of \(d_x\) and \(p_x\) before the first iteration, and \(d^{(i)}_x\) and \(p^{(i)}_x\) to refer to the values of \(d_x\) and \(p_x\) at the end of the \(i\)th iteration.

To test whether \(G^f\) contains a negative cycle, we use the Bellman-Ford algorithm as follows: First we add a new vertex \(s\) to \(G^f\) along with an edge of length \(0\) from \(s\) to every vertex \(x \in G^f\). This ensures that every vertex in \(G^f\) is reachable from \(s\) and thus that it has a finite distance from \(s\). The length of every edge \(e \in G^f\) is chosen to be the same as its residual cost \(c^f_e\). Then we run the Bellman-Ford algorithm with \(s\) as the source, but we run it for one additional iteration, for \(n\) iterations in total (where \(n\) is the number of vertices including \(s\))!

The following claim shows that we can use the output of the Bellman-Ford algorithm to decide whether there exists a negative cycle in \(G^f\).

Claim 6.17: There exists a negative cycle in \(G^f\) if and only if \(d^{(n)}_x < d^{(n-1)}_x\) for some vertex \(x \in G^f\).¹

Proof: First assume that there is no negative cycle in \(G^f\). Adding \(s\) to \(G^f\) does not introduce any negative cycle because \(s\) has only out-edges. Thus, according to the correctness proof of the Bellman-Ford algorithm, \(d^{(n-1)}_x = \mathrm{dist}_{G^f}(s,x)\) for all \(x \in G^f\). Since \(\mathrm{dist}_{G^f}(s,y) \le \mathrm{dist}_{G^f}(s,x) + c^f_{x,y}\) for every edge \((x,y) \in G^f\), this implies that \(d^{(n-1)}_y \le d^{(n-1)}_x + c^f_{x,y}\) for every edge \((x,y) \in G^f\), that is,

\[d^{(n)}_y = \min\left(d^{(n-1)}_y, \min_{(x,y) \in G^f}\left(d^{(n-1)}_x + c^f_{x,y}\right)\right) = d^{(n-1)}_y \quad \forall y \in G^f.\]

Thus, there is no vertex \(y \in G^f\) with \(d^{(n)}_y < d^{(n-1)}_y\).

Conversely, assume that \(d^{(n)}_y = d^{(n-1)}_y\) for every vertex \(y \in G^f\). Then

\[d^{(n-1)}_y \le d^{(n-1)}_x + c^f_{x,y} \quad \forall (x, y) \in G^f.\]

Let \(C = \langle x_0, \ldots, x_r \rangle\) be any cycle in \(G^f\). Then

\[d^{(n-1)}_{x_r} \le d^{(n-1)}_{x_0} + \sum_{i=1}^r c^f_{x_{i-1},x_i},\]

which implies that

\[0 \le \sum_{i=1}^r c^f_{x_{i-1}, x_i} = c^f(C)\]

because \(x_0 = x_r\). Thus, there is no negative cycle in \(G^f\). ▣

After spending \(O(nm)\) time to run the Bellman-Ford algorithm, Claim 6.17 allows us to decide in \(O(n)\) time whether \(G^f\) contains a negative cycle. If there exists a negative cycle in \(G^f\), we find such a cycle as follows: We choose an arbitrary vertex \(x_0\) that satisfies \(d^{(n)}_{x_0} < d^{(n-1)}_{x_0}\) and set \(i = 0\). As long as \(p^{(n)}_{x_i} \ne s\) and \(p^{(n)}_{x_i} \notin \{x_0, \ldots, x_i\}\), we define \(x_{i+1} = p^{(n)}_{x_i}\) and increase \(i\) by one. We prove below that the situation when \(p^{(n)}_{x_i} = s\) never arises. Thus, the algorithm exits only when it determines that \(p^{(n)}_{x_i} \in \{x_0, \ldots, x_i\}\). In this case, there exists a unique index \(0 \le j \le i\) such that \(p^{(n)}_{x_i} = x_j\). We prove below that \(C = \langle x_{i+1}, x_i, \ldots, x_j \rangle\) is a negative cycle in \(G^f\). Finding \(C\) in this fashion clearly takes \(O(n)\) time: We start by marking all vertices as unexplored, marking \(x_0\) as explored, and setting \(C = \langle x_0 \rangle\). As long as \(p^{(n)}_{x_i}\) is unexplored, we prepend it to \(C\) and mark it as explored. This takes constant time, and we can do this at most \(n\) times because there are only \(n\) vertices we can add to \(C\). When \(p^{(n)}_{x_i}\) is explored, we find its occurrence \(x_j \in C\) and remove all vertices that come after \(x_j\) in \(C\) from \(C\). This clearly takes \(O(|C|) = O(n)\) time.

To prove that this procedure does indeed find a negative cycle in \(G^f\), we need the following observation, which should be obvious:

Observation 6.18: For all \(0 \le i \le n\), \(d^{(i)}_y\) is the length of a shortest walk² from \(s\) to \(y\) with at most \(i\) edges. If \(d^{(i)}_y \ne \infty\) and \(y \ne s\), then \(d^{(i)}_y = d^{(i-1)}_{p^{(i)}_y} + c^f_{p^{(i)}_y, y}\).

To complete the correctness proof of our negative cycle finding algorithm, we prove first that the termination condition \(p^{(n)}_{x_i} = s\) is never reached. Assume the contrary and consider the path \(P = \langle x_{i+1}, x_i, \ldots, x_0 \rangle\), where \(x_{i+1} = p^{(n)}_{x_i} = s\). By Observation 6.18, we have

\[\begin{aligned} d^{(n)}_{x_h} &= d^{(n-1)}_{p^{(n)}_{x_h}} + c^f_{p^{(n)}_{x_h}, x_h}\\ &= d^{(n-1)}_{x_{h+1}} + c^f_{x_{h+1}, x_h}\\ &\ge d^{(n)}_{x_{h+1}} + c^f_{x_{h+1}, x_h} \end{aligned}\]

for all \(0 \le h \le i\). Thus,

\[d^{(n)}_{x_0} \ge \sum_{h=0}^i c^f_{x_{h+1}, x_h} = c^f_P \ge d^{(n-1)}_{x_0}.\]

The last inequality follows because \(P\) visits at most \(n\) vertices and thus has at most \(n - 1\) edges and, by Observation 6.18, \(d^{(n-1)}_{x_0}\) is the length of a shortest walk from \(s\) to \(x_0\) with at most \(n - 1\) edges. However, \(x_0\) was chosen so that \(d^{(n)}_{x_0} < d^{(n-1)}_{x_0}\). We have arrived at a contradiction. Thus, when the algorithm terminates, we have \(p^{(n)}_{x_i} = x_j\) for some \(0 \le j \le i\). It remains to prove that \(C = \langle x_{i+1}, x_i, \ldots, x_j \rangle\) is a negative cycle in \(G^f\).

Since \(x_{h+1} = p^{(n)}_{x_h}\) for all \(0 \le h \le i\), \(G^f\) contains the edge \((x_{h+1}, x_h)\) for all \(0 \le h \le i\). Since \(x_{i+1} = p^{(n)}_{x_i} = x_j\), \(C\) is thus a cycle in \(G^f\). It remains to prove that its cost is negative.

Let \(m\) be the minimum index such that \(d^{(m)}_{x_h} = d^{(n)}_{x_h}\) for all \(x_h \in C\). Then there exists a vertex \(x_h \in C\) such that \(d^{(m)}_{x_h} \ne d^{(m-1)}_{x_h}\). Since \(d^{(i)}_{x_h} \le d^{(i-1)}_{x_h}\) for all \(i\), we thus have \(d^{(m)}_{x_h} < d^{(m-1)}_{x_h}\). Let us rename the vertices in \(C\) as \(C = \langle x_h = y_0, \ldots, y_{i-j-1} = x_h \rangle\). Then

\[d^{(m-1)}_{y_k} \ge d^{(m)}_{y_k} = d^{(m-1)}_{y_{k-1}} + c^f_{y_{k-1},y_k} \ge d^{(m)}_{y_{k-1}} + c^f_{y_{k-1},y_k} \quad \forall 1 \le k \le i - j - 1\]

because \(y_{k-1} = p^{(m)}_{y_k}\) for all \(1 \le k \le i - j - 1\). Thus,

\[\begin{aligned} d^{(m-1)}_{x_h} > d^{(m)}_{x_h} &\ge d^{(m-1)}_{x_h} + \sum_{k=1}^{i-j-1} c^f_{y_{k-1},y_k}\\ 0 &> \sum_{k=1}^{i-j-1} c^f_{y_{k-1},y_k} = c^f_C, \end{aligned}\]

that is, \(C\) is a negative cycle. ▨

We are ready to state the main result of this section:

Theorem 6.19: The negative cycle cancelling algorithm takes \(O\bigl(nm^2 CU\bigr)\) time to compute a minimum-cost flow in a network whose vertices have integer supply balances between \(-U\) and \(U\) and whose edges have integer capacities no greater than \(U\) and integer costs between \(-C\) and \(C\).

Proof: Finding an initial flow using any of the maximum flow algorithms from the previous chapter takes \(O\bigl(nm^2\bigr)\) time. By Lemma 6.16, finding a negative cycle takes \(O(nm)\) time and it is easy to see that updating the flow using this negative cycle also takes \(O(nm)\) time. Thus, it suffices to prove that the second phase of the algorithm runs for at most \(mCU\) iterations.

The initial flow has cost at most \(m_1CU\), where \(m_1\) is the number of edges with positive cost: Every edge carries at most \(U\) units of flow and has a cost of at most \(C\), so it contributes at most \(CU\) to the cost of the flow. By an analogous argument, the final flow has cost at least \(-m_2CU\), where \(m_2\) is the number of edges with negative cost because every edge carries at most \(U\) units of flow and has cost at least \(-C\). Now observe that sending any flow along a negative cycle in \(G^f\) strictly decreases the cost of the flow. Since the flow, and thus its cost, is integral at all times, each iteration of the second phase therefore decreases the cost of the flow by at least \(1\). Since the second phase starts with a flow of cost at most \(m_1CU\) and terminates with a flow of cost at least \(-m_2CU\), this implies that the algorithm terminates after at most \((m_1 + m_2)CU \le mCU\) iterations. ▨