(O(N2/3A) Complexity for Unit Capacity Graphs) Consider the max-flow problem in the special case where the arc flow range is [0,1] for all arcs. (a) Show that each path from the source to the sink that is unblocked with respect to the zero flow has at most 2N/√M arcs, where M is the value of the maximum flow. Hint: Let Nk be the number of nodes i such that the shortest unblocked path from s to i has k arcs. Argue that k(k + 1) ≥ M. (b) Show that the running time of the layered network algorithm (cf. Fig. 3.8) is reduced to O(N2/3A).
(a) Solve the problem of Exercise 3.1 using the layered network algorithm (cf. Fig. 3.8).
(b) Construct an example of a max-flow problem where the layered network algorithm requires N - 1 phases.