# Finding negative cycles for cycle-canceling algorithm

I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is lowered in each round. To find a negative cycle I am using the bellman-ford algorithm.

My Problem is: Bellman-ford only finds cycles that are reachable from the source, but I also need to find cycles that are not reachable.

Example: In the following network, we already applied a maximum flow. The edge $(A, B)$ makes it very expensive. In the residual network, we have a negative cost cycle with capacity $1$. Removing it, would give us a cheaper solution using edges $(A, C)$ and $(C, T)$, but we cannot reach it from the source $S$.

Labels: Flow/Capacity, Cost Of course, I could run Bellman-ford repeatedly with each node as source, but that does not sound like a good solution. I'm a little confused because all the papers I read seem to skip this step.

Can you tell me, how to use bellman-ford to find every negative cycle (reachable or not)? And if not possible, which other algorithm do you propose?

• If a cycle cannot be reached via the source, how can it affect the total flow? – Nicholas Mancuso Nov 19 '12 at 21:30
• It won't affect the flow value but the total cost. See the new example. – Patrick Schmidt Nov 19 '12 at 21:39
• I think you should be running Bellman-Ford from the sink, no? If you find a maximum flow, $f$, then under the residual graph $G_f$ there will not be a path from $s$ to $t$. Therefore, Bellman-Ford should be run on $G_f$ with $t$. – Nicholas Mancuso Nov 20 '12 at 1:44

## 3 Answers

To expand upon my comment, remember, this algorithm for finding Min-Cost-Flow relies on the fact that $f$ is maximal. By first running Ford-Fulkerson to find $f$ and the resulting residual network $G_f$, the cost $f$ is then reduced by finding negative cycles in $G_f$. That is, by finding negative cycles in $G_f$ we do not change the amount of flow, $f$, but merely the cost.

Now by running Bellman-Ford from $t$ in $G_f$ we can trace backwards on edges that have non-negative flow (by definition of $G_f$). If cycles are adjacent to any edges in these paths, then we can "transfer" some amount of flow to other edges in the cycle. In other words, we keep the net-flow for some cycle the same, but are able to change the cost.

Notice an unreachable cycle from $t$ must have zero-flow. Otherwise we would have a contradiction in $f$ being maximal.

I apologize for the "hand-wavy-ness" of this explanation. I will try to be more formal when I have time tonight.

• Thanks, your last sentence makes it clear. So, it is enough to deal with cycles which are reachable from $T$. – Patrick Schmidt Nov 20 '12 at 17:46

My suggestion: You have to start the algorithm from T, in order to find a negative cycle in your residual network. The result should be the same, but then you can reach the circle

• This works for this graph, but you can have negative cycles that aren't connected to either S or T. I suspect that the OP wants a solution that works in general. – Peter Shor Nov 20 '12 at 12:15
• yes, in general you cant find every negative cycle, but the OP wants to improve his residual Network by checking the costs. Then unreachable negative circles dont matter – Sven Jung Nov 20 '12 at 13:06
• I want to use this to get a min cost flow. So the new question would be: Is it sufficient to eliminate every cycle that is reachable from the sink $T$ (In the residual network). Right now I can't find a counter example – Patrick Schmidt Nov 20 '12 at 13:12
• You can view a flow as either originating at $S$ and going to $T$, or reverse every edge and view it as originating at $T$ and going to $S$. If eliminating every cycle that is reachable from the source $S$ doesn't work, then eliminating every cycle that is reachable from the sink $T$ won't work. The source and the sink behave symmetrically. – Peter Shor Nov 20 '12 at 13:37
• of course it is the same if you reverse every edge and start from T, because nothing changed. But why dont start at T without reversing the edges?then you should find a reachable negative cycle, if existing. The question is, if the unreachable negative cycles really dont matter – Sven Jung Nov 20 '12 at 13:53

I think it's not sufficient to run Bellman-Ford from T or S. Consider one example where there is one edge from S to T and one negative-cost cycle not achievable from neither S or T.

One solution is to add an auxiliary S' and add an edge from S' to any other vertex with 0 cost. Then run Bellman-Ford from S'. In this way, all negative cycles are reachable from S'.

Furthermore, you don't really need to add that auxiliary vertex S' in your implementation. Just initialize d(v)=0 for any vertex v.

See how Boost Graph Library implement it.