Finding a Circulation in a Network with lower bounds

Question

I can't understand how to find circulation flow in the network with lower bounds(not demands). I found next documents with problem description and solving strategies:

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

Lets consider a network with following edges(l - lower bound, c - capacity):

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

As I understand to solve the problem we should make next steps:

1. transform this problem to "circulation with demands problem". This can be done with next formula dv' = dv - (Lin - Lout), where 'dv' is original vertex demand(in our case it's equals to zero), 'Lin' - sum of vertex input edges lower bounds, and 'Lout' - sum of vertex output edges lower bounds.
2. update edges capacities as c' = c - l
3. add source vertex S with edges to each vertex with dv < 0 with capacities '-dv'
4. add sink vertex T with edges from each vertex with dv > 0 with capacities 'dv'
5. find max-flow in the new network with any of algorithms, for example Edmonds-Karp algorithm.
6. if value of the maximum flow equals to the sum of all demands for vertices with connections to T, then there is a circulation in the network.

After performing these steps new network will be:

S -> 2 : c = 1

2 -> 3 : c = 2

3 -> T : c = 1

1 -> 2 : c = 2

3 -> 1 : c = 1

demands for vertices:

d1 = 0

d2 = -1

d3 = 1

We see that maximum flow equals to 1, and equals to the sum of edges to T which is also 1. And it cover edges A->2->3->T.

The question is how get circulation flow in the original network with original bounds?

Circulation flow in the original network exists - we need just assign flow equals to 2 to all edges.

Stanchion

Did you manage to find solution eventually? I am just started week 3, looks like many people end up on this week :) – Aparejo

Answer 1

It is a bit late, but I stumbled upon this question when working on a solution for this problem.

If you do it the other way, which is:

1. Steps 1 and 2 as in your question.
2. Add vertex S with edges to each vertex with dv > 0 with capacities 'dv'
3. Add vertex T with edges from each vertex with dv < 0 with capacities '-dv'

After this, the solution found by any max flow algorithm will be:

• S->3 : c=1
• 3->1 : c=1
• 1->2 : c=1
• 2->T : c=1

What you need to do now is just add the values of lower bounds to the result of previous steps. In this case:

• 1->2 : c=1, l=1, c+l = 2
• 2->3 : c=0, l=2, c+l = 2
• 3->1 : c=1, l=1, c+l = 2

And you have the answer you were looking for. I hope this helps somebody.

Teammate