26-5 Maximum flow by scaling

Let $G = (V, E)$ be a flow network with source $s$, sink $t$, and an integer capacity $c(u, v)$ on each edge $(u, v) \in E$. Let $C = \max_{(u, v) \in E} c(u, v)$.

a. Argue that a minimum cut of $G$ has capacity at most $C|E|$.

b. For a given number $K$, show how to find an augmenting path of capacity at least $K$ in $O(E)$ time, if such a path exists.

We can use the following modification of $\text{FORD-FULKERSON-METHOD}$ to compute a maximum flow in $G$:

MAX-FLOW-BY-SCALING(G, s, t)
    C = max_{(u, v) ∈ E} c(u, v)
    initialize flow f to 0
    K = 2^{floor(lg C)}
    while K ≥ 1
        while there exists an augmenting path p of capacity at least K augment flow f along p
        K = K / 2
    return f

c. Argue that $\text{MAX-FLOW-BY-SCALING}$ returns a maximum flow.

d. Show that the capacity of a minimum cut of the residual network $G_f$ is at most $2K|E|$ each time line 4 is executed.

e. Argue that the inner while loop of lines 5–6 executes $O(E)$ times for each value of $K$.

f. Conclude that $\text{MAX-FLOW-BY-SCALING}$ can be implemented so that it runs in $O(E^2\lg C)$ time.

a. Since the capacity of a cut is the sum of the capacity of the edges going from a vertex on one side to a vertex on the other, it is less than or equal to the sum of the capacities of all of the edges. Since each of the edges has a capacity that is $\le C$, if we were to replace the capacity of each edge with $C$, we would only be potentially increasing the sum of the capacities of all the edges. After so changing the capacities of the edges, the sum of the capacities of all the edges is equal to $C|E|$, potentially an overestimate of the original capacity of any cut, and so of the minimum cut.

b. Since the capacity of a path is equal to the minimum of the capacities of each of the edges along that path, we know that any edges in the residual network that have a capacity less than $K$ cannot be used in such an augmenting path. Similarly, so long as all the edges have a capacity of at least $K$, then the capacity of the augmenting path, if it is found, will be of capacity at least $K$. This means that all that needs be done is remove from the residual network those edges whose capacity is less than $K$ and then run BFS.

c. Since $K$ starts out as a power of $2$, and through each iteration of the while loop on line 4, it decreases by a factor of two until it is less than $1$. There will be some iteration of that loop when $K = 1$. During this iteration, we will be using any augmenting paths of capacity at least $1$ when running the loop on line 5. Since the original capacities are all integers, the augmenting paths at each step will be integers, which means that no augmenting path will have a capacity of less than $1$. So, once the algorithm terminates, there will be no more augmenting paths since there will be no more augmenting paths of capacity at least $1$.

d. Each time line 4 is executed we know that there is no augmenting path of capacity at least $2K$. To see this fact on the initial time that line 4 is executed we just note that $2K = 2 \cdot 2^{\lfloor \lg C \rfloor} > 2 \cdot 2^{\lg C − 1} = 2^{\lg C} = C$. Then, since an augmenting path is limited by the capacity of the smallest edge it contains, and all the edges have a capacity at most $C$, no augmenting path will have a capacity greater than that. On subsequent times executing line 4, the loop of line 5 during the previous execution of the outer loop will of already used up and capacious augmenting paths, and would only end once there are no more.

Since any augmenting path must have a capacity of less than $2K$, we can look at each augmenting path $p$, and assign to it an edge $e_p$ which is any edge whose capacity is tied for smallest among all the edges along the path. Then, removing all of the edges $e_p$ would disconnect the residual network since every possible augmenting path goes through one of those edge. We know that there are at most $|E|$ of them since they are a subset of the edges. We also know that each of them has capacity at most $2K$ since that was the value of the augmenting path they were selected to be tied for cheapest in. So, the total cost of this cut is $2K|E|$.

e. Each time that the inner while loop runs, we know that it adds an amount of flow that is at least $K$, since that’s the value of the augmenting path. We also know that before we start that while loop, there is a cut of cost $\le 2K|E|$. This means that the most flow we could possibly add is $2K|E|$. Combining these two facts, we get that the most cuts possible is $\frac{2K|E|}{K} = 2|E| \in O(|E|)$.

f. We only execute the outermost for loop $\lg C$ many times since $\lg(2^{\lfloor \lg C \rfloor}) \le \lg C$. The inner while loop only runs $O(|E|)$ many times by the previous part. Finally, every time the inner for loop runs, the operation it does can be done in time $O(|E|)$ by part (b). Putting it all together, the runtime is $O(|E|^2\lg C)$.