Increase flow by changing only one edge after Ford-Fulkerson

Question

Suppose that I've run the Ford-Fulkerson algorithm on a graph G = (V,E) and the result is a max-flow f_max, which is associated to a min-cut Xmin. I'm interested in increasing the flow as much as possible by increasing the capacity of any one edge in the graph. How can I identify this edge?

One strategy might be: given the the initial vertex s and the final vertex t, consider all the paths from s to t and verify the edge with lower capacity. For example, if I have an edge with 1/1, this is the vertex that I have to increase the capacity.

Is there a general algorithm for solving this problem?

Answer 1

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!