Maximum flow by scaling Let G D .V; E/ be a flow network

Chapter 26, Problem 26-5

(choose chapter or problem)

Maximum flow by scaling Let G D .V; E/ be a flow network with source s, sink t, and an integer capacity c.u; / on each edge .u; / 2 E. Let C D max.u; /2E c.u; /. a. Argue that a minimum cut of G has capacity at most C jEj. 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 FORD-FULKERSON-METHOD to compute a maximum flow in G: MAX-FLOW-BY-SCALING.G; s; t/ 1 C D max.u; /2E c.u; / 2 initialize flow f to 0 3 K D 2blgCc 4 while K 1 5 while there exists an augmenting path p of capacity at least K 6 augment flow f along p 7 K D K=2 8 return f c. Argue that MAX-FLOW-BY-SCALING returns a maximum flow. d. Show that the capacity of a minimum cut of the residual network Gf is at most 2K jEj each time line 4 is executed. e. Argue that the inner while loop of lines 56 executes O.E/ times for each value of K. f. Conclude that MAX-FLOW-BY-SCALING can be implemented so that it runs in O.E2 lgC / time.