In Section we considered the Preflow-Push Algorithm, and discussed one particular selectio...

In Section we considered the Preflow-Push Algorithm, and discussed one particular selection rule for considering vertices. Here we will explore a different selection rule. We will also consider variants of the algorithm that terminate early (and find a cut that is close to the minimum possible).

(a) Let f be any preflow. As f is not necessarily a valid flow, it is possible that the value fout(s) is much higher than the maximum-flow value in G. Show, however, that fin(t) is a lower bound on the maximum-flow value.

(b) Consider a preflow f and a compatible labeling h. Recall that the set A = {v: There is an s-v path in the residual graph Gf}, and B = V–A defines an s-t cut for any preflow f that has a compatible labeling h. Show that the capacity of the cut (A, B) is equal to A = ∑vεBef(v)

Combining (a) and (b) allows the algorithm to terminate early and return (A, B) as an approximately minimum-capacity cut, assuming c(A, B) – fin(t) is sufficiently small. Next we consider an implementation that will work on decreasing this value by trying to push flow out of nodes that have a lot of excess.

(c) The scaling version of the Preflow-Push Algorithm maintains a scaling parameter ∆.Weset ∆A initially to be a large power of 2. The algorithm at each step selects a node with excess at least ∆ with as small a height as possible. When no nodes (other than t) have excess at least ∆, we divide ∆ by 2, and continue. Note that this is a valid implementation of the generic Preflow-Push Algorithm. The algorithm runs in phases. A single phase continues as long as ∆ is unchanged. Note that ∆ starts out at the largest capacity, and the algorithm terminates when ∆ = 1. So there are at most 0(log C) scaling phases. Show how to implement this variant of the algorithm so that the running time can be bounded by O(mn + n log C + K) if the algorithm has K nonsaturating push operations.

(d) Show that the number of nonsaturating push operations in the above algorithm is at most O(n2 log C). Recall that O(log C) bounds the number of scaling phases. To bound the number of nonsaturating push operations in a single scaling phase, consider the potential function  What is the effect of a nonsaturating push on Φ? Which operation(s) can make Φ increase?