Once you have found the maximum flow in the graph, increasing the capacity of an edge (u, v) will only increase the maximum flow if there is a positive-capacity path from s to u and from v to t in the residual graph. If this isn't the case, then there won't be an augmenting path in the residual graph after making the increase, and therefore the maximum flow will remain maximum.
Of the edges (u, v) that have this property, the maximum amount of extra flow that you can push from s to t after increasing the capacity of (u, v) will be bounded. If you can push any flow across this edge, you'll have to do so by finding a path from s to u and a path from v to t. When doing so, there will always be a bottleneck edge in each of the two paths, and the flow can't increase by more than this. Accordingly, one option for solving the problem is to do the following:
- Find the maximum-bottleneck path from s to each other node reachable from s in the residual graph.
- Find the maximum-bottleneck path from each node that can reach t to t in the residual graph.
- For each edge (u, v) crossing the path, the maximum amount of extra flow that can be pushed across the edge is given by the minimum of the max-bottleneck path from s to u and the max-bottleneck path from v to t.
In other words, if you can compute maximum-bottleneck paths in the graph, you can find the edge that should be increased in time O(B(m, n) + m), where B(m, n) is the cost of computing maximum-bottleneck paths in the graph.
Fortunately, this is a well-studied problem and can be solved using a variant of Dijkstra's algorithm where instead of storing minimum-cost paths to each node, you store maximum-bottleneck paths to each node. A quick Google search should turn up some additional information on this. Using a Fibonacci heap, you can implement this search in time O(m + n log n), and therefore the overall runtime for identifying the edge whose capacity should be increased should be O(m + n log n) as well.
Hope this helps!
