Menu
Suppose that I've run the Ford-Fulkerson algorithm on a graph G = (V,E) and the result is a max-flow fmax, 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?
916
When all the edges have the same capacity, increasing the capacity of every edge by 1 will not change the minimum cut. The basic idea behind the proof is that the capacity of a cut is nc where n is the number of edges cut, and c is the capacity of each edge.
You can do this by essentially finding a path from source to sink along your flow that goes through the decremented edge (this is not hard to do, just start from the decremented edge and "follow" the flow). Then, subtract 1 from your flow for each edge in that path.
The complexity of Ford-Fulkerson algorithm cannot be accurately computed as it all depends on the path from source to sink. For example, considering the network shown below, if each time, the path chosen are S − A − B − T and S − B − A − T alternatively, then it can take a very long time.
In some cases, you would need to increase the capacity of all edges of the graph in order to increase the max-flow. A way to test that is to compute the min-cut, then try and increase the capacity on one or several edges of this min-cut, and recompute the flow to compare to its previous value.
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:
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!
191
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
