Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, find a total extra capacity needed E so that maximum flow from source to sink is greater than or equal to F and flow in each edge that has nonzero flow.

I don't know how to solve this variation of maximum flow problem. It is obvious that if maximum flow I find without extra capacities is greater than or equal to F, then there is no need for extra capacity. If it is less than F, should I add extra capacity in each edge one by one and find max flow again till I find the closest one to F (if it is not enough, then take in pairs, triplets, etc.)? This solution seems inefficient to me.

  • $\begingroup$ How are you measuring total extra capacity? The sum of the extra capacities used across each edge? The maximum extra capacity used across an edge? $\endgroup$ – templatetypedef Jan 4 '15 at 17:10
  • $\begingroup$ E is a sum of extra capacities used across each edge $\endgroup$ – Kudayar Pirimbaev Jan 4 '15 at 17:11
  • $\begingroup$ it's my question, this one migrated too late $\endgroup$ – Kudayar Pirimbaev Jan 5 '15 at 0:02