The goal of this problem is to suggest variants of the Preflow-Push Algorithm that speed u...

The goal of this problem is to suggest variants of the Preflow-Push Algorithm that speed up the practical running time without ruining its worst-case complexity. Recall that the algorithm maintains the invariant that h(v) ≤ h(w) + 1 for all edges (v, w) in the residual graph of the current preflow. We proved that if f is a flow (not just a preflow) with this invariant, then it is a maximum flow. Heights were monotone increasing, and the running-time analysis depended on bounding the number of times nodes can increase their heights. Practical experience shows that the algorithm is almost always much faster than suggested by the worst case, and that the practical bottleneck of the algorithm is relabeling nodes (and not the nonsaturating pushes that lead to the worst case in the theoretical analysis). The goal of the problems below is to decrease the number of relabelings by increasing heights faster than one by one. Assume you have a graph G with n nodes, m edges, capacities c, source s, and sink t.

(a) The Preflow-Push Algorithm, as described in Section starts by setting the flow equal to the capacity ce on all edges e leaving the source, setting the flow to 0 on all other edges, setting h(s) = n, and setting h(v) = 0 for all other nodes v e V. Give an O(m) procedure for initializing node heights that is better than the one we constructed in Section. Your method should set the height of each node v to be as high as possible given the initial flow.

(b) In this part we will add a new step, called gap relabeling, to Preflow-Push, which will increase the labels of lots of nodes by more than one at a time. Consider a preflow f and heights h satisfying the invariant. A gap in the heights is an integer 0 h(v)> h. Gap relabeling is the process of changing the heights of all nodes in A so they are equal to n. Prove that the Preflow-Push Algorithm with gap relabeling is a valid max-flow algorithm. Note that the only new thing that you need to prove is that gap relabeling preserves the invariant above, that h(v) ≤ h(w) + 1 for all edges (v, w) in the residual graph.

(c) In Section we proved that h(v) ≤ 2n – 1 throughout the algorithm. Here we will have a variant that has h(v)

(d) The algorithm in part (c) computes a minimum s-t cut but fails to find a maximum flow (as it ends with a preflow that has excesses). Give an algorithm that takes the preflow f at the end of the algorithm of part (c) and converts it into a maximum flow in at most O(mn) time. (Hint: Consider nodes with excess, and try to send the excess back to s using only edges that the flow came on.)