9
$\begingroup$

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

enter image description here

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?

Improve this question
$\endgroup$
  • $\begingroup$ If a cycle cannot be reached via the source, how can it affect the total flow? $\endgroup$ – Nicholas Mancuso Nov 19 '12 at 21:30
  • $\begingroup$ It won't affect the flow value but the total cost. See the new example. $\endgroup$ – Patrick Schmidt Nov 19 '12 at 21:39
  • 2
    $\begingroup$ 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$. $\endgroup$ – Nicholas Mancuso Nov 20 '12 at 1:44
2
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 20 '12 at 12:15
  • $\begingroup$ 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 $\endgroup$ – Sven Jung Nov 20 '12 at 13:06
  • $\begingroup$ 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 $\endgroup$ – Patrick Schmidt Nov 20 '12 at 13:12
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 20 '12 at 13:37
  • $\begingroup$ 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 $\endgroup$ – Sven Jung Nov 20 '12 at 13:53
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.