Increase flow by changing only one edge after Ford-Fulkerson

Question

Suppose that I performed the Ford-Fulkerson algorithm on the graph G = (V, E), and the result is the maximum flow f _max , which is associated with the mini-section Xmin. I am interested in increasing the flow as much as possible by increasing the throughput of any edge on the graph. How can I identify this edge?

One strategy could be: taking into account the initial vertex s and the final vertex t, consider all the paths from s to t and check the edge with less bandwidth. For example, if I have an edge with 1/1, this is the vertex that I have to increase capacity.

Is there a general algorithm for solving this problem?

Answer 1

As soon as you find the maximum flow on the graph, increasing the edge capacity (u, v) will increase the maximum flow if there is a path of positive capacity from s to u and from v to t to the residual graph. If this is not so, then after the increase there will be no expansion path on the residual graph, and therefore the maximum flow will remain maximum.

Of the edges (u, v) having this property, the maximum number of additional flow that you can press from s to t after increasing the capacity (u, v) will be limited. If you can click any thread along this edge, you will have to do this by finding the path from s to u and the path from v to t. In this case, there will always be an edge of a bottleneck on each of the two paths, and the flow cannot increase by more than this. Accordingly, one of the solutions to the problem is as follows:

• To find the path with the maximum bottleneck from s to each other, the node is reachable from s in the residual graph.
• Find the path with the maximum bottleneck 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 additional flow that can be shifted over the edge is determined by the minimum path max-bottleneck from s to u and max-bottleneck path from v to t.

In other words, if you can calculate the maximum bottleneck paths in a 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 calculating the maximum bottleneck paths on the chart.

Fortunately, this is a well-studied problem and can be solved using a variant of the Dijkstra algorithm, where instead of storing the minimum cost paths for each node, you save the paths with the maximum bottleneck for each node. A quick Google search should contain more information about this. Using the Fibonacci heap, you can implement this time search O (m + n log n), and therefore the total execution time to determine the edge whose capacity should be increased should be O (m + n log n).

Hope this helps!