3
$\begingroup$

Problem:

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.

EDIT:

Example:

Suppose source is node 0 and sink is node 5. Sink requires flow of 6 (F = 6). For the following format

(1st node, 2nd node), current capacity, extra capacity that can be added

we have following edges

0 1 3 0
0 3 3 0
1 2 3 0
1 3 2 0
2 4 4 0
2 5 2 2
3 4 2 1
4 5 3 1

Maximum flow from current capacities is 5 which is not enough for the sink (5 < F). The extra capacity from 3 to 4 and 4 to 5 is required. So total extra capacity is 2 (E = 2) and the flows are

0 1 3
0 3 3
1 2 3
2 4 1
2 5 2
3 4 3
4 5 4
Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Please explain how the "extra capacity" works. It's not at all obvious. $\endgroup$
    – David Richerby
    Jan 5, 2015 at 0:53
  • $\begingroup$ editted question $\endgroup$
    – Kudayar Pirimbaev
    Jan 5, 2015 at 4:24
  • 1
    $\begingroup$ It may help to rephrase the question in terms of demand (instead of required flow) and capacity. Then you should consider writing the LP form of minimizing the total offsets needed to satisfy demand. $\endgroup$
    – Nicholas Mancuso
    Jan 5, 2015 at 6:04

1 Answer 1

Reset to default
1
$\begingroup$

The smarter Naive approach of extending a solution to the Maximum Flow problem to a similar graph with at least as much capacity is to only add flow to augmenting paths that you'd find from the Residual of the initial graph. And if no augmenting paths exist, then terminate. This is known as the Ford-Fulkerson Algorithm, and if you were to have run it on the a graph of $E$ edges initially, this would incur a runtime of $O(E\cdot f^*)$, where $f^*$ is the maximum flow in the graph.

In case you haven't heard of some of these terms, or the Algorithm, visit: http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.