# 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

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
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