CODEWITHSUNDEEP
algorithmgraph
The Baron
The Baron

Reputation: 123

Max flow along cycles

I have a directed graph, and I want to find the maximal amount of flow that I can send along cycles(loops). Can the standard Ford-Fulkerson approach work, with augmenting paths(cycles in this case), or do I need something special? There's no source/sink, I just want to send flow along cycles.

The quantity I want to maximize is Sum(f(i,j)), where f(i,j) is the flow along that edge, over all edges, under the regular max. flow constraints(each edge has a non-negative finite capacity, and inflow(v)=outflow(v) for every vertex).

Upvotes: 2

Views: 8254

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

You need to do something more complicated than just augment. The problem is, as soon as you send flow along a cycle, you can either insert the backward residual arcs or not. If you do, then there's nothing stopping you from sending the flow right back where it came from. If you don't, then you can augment the wrong cycle. For example, in the graph

c-->d
^   |
|   v
b-->e
^   |
|   v
a<--f

where all arcs have unit capacity, you might augment a->b->e->f->a and miss the longer cycle a->b->c->d->e->f->a.

Instead what you have to do is run Bellman--Ford (or some other shortest-path algorithm that tolerates negative lengths) to find a cycle that has more forward arcs than backward and saturate it. (If no such cycle exists, then you have an optimal solution.) Then you get an O(OPT poly(n)) bound as in Ford--Fulkerson, where all arcs have integer capacity and OPT is the optimal objective value. You can raid the literature on circulation problems/network simplex for optimizations.

To detect a cycle with more forward arcs than backward: set the length of each forward arc to -1 and the length of each backward arc to 1. Initialize the distance label of each vertex to 0 (simulating the effect of an artificial source with no incoming arcs and length-0 arcs to each other vertex). Run Bellman--Ford to determine whether there is a negative-length cycle.

Upvotes: 1

Related Questions