# 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? Commented Nov 19, 2012 at 21:30
• It won't affect the flow value but the total cost. See the new example. Commented Nov 19, 2012 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$. Commented Nov 20, 2012 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$. Commented Nov 20, 2012 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. Commented Nov 20, 2012 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 Commented Nov 20, 2012 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 Commented Nov 20, 2012 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. Commented Nov 20, 2012 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 Commented Nov 20, 2012 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.