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.
Algorithm: Minimum maximum flow with extra capacities
algorithms;graph theory;network flow