patternMinor
Finding negative cycles for cycle-canceling algorithm
Viewed 0 times
cyclecancelingalgorithmforfindingnegativecycles
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#6773, answer score: 2
Revisions (0)
No revisions yet.