Given a flow network with maximum flow $f$, I want to find the minimum amount of edges, that if their capacity will increase, the maximum flow will increase.
I have tried using BFS to find the amount of Min-Cuts in the residual network, but I found a counterexample for this.
Is this the right direction for this problem? I'm guessing min-cuts have to have something to do with this. But what?
Best Answer
Generally in solving a maximum flow problem, one finds not only the total flow from source to sink, but the capacity limited flows on each edge of the graph (network). For example:
By Min_cut.png: Maksim derivative work: Cyhawk (Min_cut.png) CC-BY-SA-3.0 or GFDL, via Wikimedia Commons
Now the problem of the fewest edges whose capacity must be increased in order to increase the total flow can be solved as a "shortest path" problem for a related graph. Here the source node is $s$ and the sink node is $t$.
Let edges whose capacity is fully used ("tight" constraint) be assigned length one, and let edges whose capacity is less than fully used ("slack" constraint) be assigned length zero.
Then the corresponding shortest path from $s$ to $t$ will have length two:
$$ s \to p \to r \to t $$
since the edge from $s$ to $p$ has length zero in this context.
Thus we need only increase the capacities of the two "tight" edges along this path, $p$ to $r$ and $r$ to $t$, in order to increase the total flow.
In this example it is not hard to see by inspection that capacity increases to at least two edges are needed, as both $q\to t$ and $r\to t$ are tight, and also $o\to q$ and $p\to r$ are tight, and any path from $s$ to $t$ must pass through one of each of these independent pairs.