Searching for minimal flow with fulfill capacity in flow graphs

Question

I have modified task of maximum flow problems. I should find minimum flow which satisfies condition (where f is flow and c is capacity):

f(u,v) >= c(u,v) 

So flow at every edge is at least capacity of edge. (I am writing capacity but it was rename because it's no longer capacity, it's count which must be satisfied by flow)

One more thing. I have function MaxFlow which gives me classic maximal flow and I can call it once.

Can anyone help me with pseudo algorithm? I am thinking about modifing Ford-Fulkers algorithm and change it for my needs but I am not sure where to fit that MaxFlow? How it can help me with algorithm when I know maximum flow in graph? Thanks

Answer 1

There is a simple reduction from maximum flow with lower bounds to maximum flow:

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

The idea is that you saturate all edges. Then you are left with imbalanced nodes. You can use a max-flow algorithm to resolve the imbalance.

The construction works as follows: For every vertex v, define M(v) := sum of lower bounds on incoming edges - sum of lower bounds on outgoing edges. Remove all lower bounds and set capacity of each original edge to upper bound - lower bound (in your case, infinity).

Introduce a new super source S and a new super sink T. Add an edge (S, v) with upper capacity M(v) for every vertex v with M(v) >= 0. Add an edge (v, T) with upper capacity -M(v) for every vertex v with M(v) < 0.

Solve the resulting S-T maximum flow problem.

Finally, remove S and T and add the original lower bound to the flow on every original edge.