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.