We given a network with K
vertexes and give a
and b
. capacity of all edges is infinite
. for a flow from a
to b
, the edge that pass max flow
through it, called bottleneck edge and capacity of transferred flow through that edge is called bottleneck of flow. an integer M
is given. we want transfer flow with size M
with lowest bottleneck from a to b. how many times we should used ford-Fulkerson to calculate this flow?
O(1) runs is the answer, but how?
Say you assign each edge a capacity 1, run FF a single time, and get the resulting graph. Moreover, let the max flow be M'. Intuitively, we find that the min cut is $M'$, meaning that there are M' edge-disjoint paths from a to b in this case. This tells us how to get to a solution of ⌈ M / M' ⌉, by scaling the flows appropriately. For example, suppose that $M=5$, and when setting the capacities to 1, we get $M' = 2$. Then we know that the min-cut is 2. If we increase the capacity to 5 / 2 = 2.5, then we would get exactly the flow of 5 to begin with. Since this is a non-integer, we would increase the capacity of some edges (forming a path from a to b) to 3, and some to 2.
You cannot get anything lower than what was just found. If you could get something lower, say M'' < ⌈ M / M' ⌉, then if you would set the capacity of all edges to M'', the flow would not change. By the max-flow / min-cut theorem, this means that there is a min-cut of M / M'' > M' edges. This contradicts the min cut being only M'.
nice algorithm +1. what is the role of scaling the flows means intuitively in simple words for this question?
I've updated the answer to clarify some points. Hope this helps.
@MK If M=10 and M'=5, then the scaling is 2, as you state. The bottleneck in this case is 2. Not sure what you're asking me to correct.
@MK If the M = 10, and M' = 2, then the bottleneck is 5, and there are 2 edge-disjoint paths from a to b. If you scale the capacity of all edges to 5, then each path gives 5, and the overall flow is 10, which is exactly M.