Algorithmic consulting Professor Gore wants to open up an

Escape problem An n n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in Figure 26.11. We denote the vertex in the ith row and the j th column by .i; j /. All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points .i; j / for which i D 1, i D n, j D 1, or j D n. Given m n2 starting points .x1; y1/; .x2; y2/; : : : ; .xm; ym/ in the grid, the escape problem is to determine whether or not there are m vertex-disjoint paths from the starting points to any m different points on the boundary. For example, the grid in Figure 26.11(a) has an escape, but the grid in Figure 26.11(b) does not. a. Consider a flow network in which vertices, as well as edges, have capacities. That is, the total positive flow entering any given vertex is subject to a capacity constraint. Show that determining the maximum flow in a network with edge and vertex capacities can be reduced to an ordinary maximum-flow problem on a flow network of comparable size. (a) (b) Figure 26.11 Grids for the escape problem. Starting points are black, and other grid vertices are white. (a) A grid with an escape, shown by shaded paths. (b) A grid with no escape. b. Describe an efficient algorithm to solve the escape problem, and analyze its running time.

Minimum path cover A path cover of a directed graph G D .V; E/ is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. A minimum path cover of G is a path cover containing the fewest possible paths. a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph G D .V; E/. (Hint: Assuming that V D f1; 2; : : : ; ng, construct the graph G0 D .V 0 ; E0 /, where V 0 D fx0; x1;:::;xng [ fy0; y1;:::;yng ; E0 D f.x0; xi/ W i 2 V g [ f.yi; y0/ W i 2 V g [ f.xi; yj / W .i; j / 2 Eg ; and run a maximum-flow algorithm.) b. Does your algorithm work for directed graphs that contain cycles? Explain.

Algorithmic consulting Professor Gore wants to open up an algorithmic consulting company. He has identified n important subareas of algorithms (roughly corresponding to different portions of this textbook), which he represents by the set A D fA1; A2;:::;Ang. In each subarea Ak, he can hire an expert in that area for ck dollars. The consulting company has lined up a set J D fJ1; J2;:::;Jmg of potential jobs. In order to perform job Ji, the company needs to have hired experts in a subset Ri A of subareas. Each expert can work on multiple jobs simultaneously. If the company chooses to accept job Ji , it must have hired experts in all subareas in Ri , and it will take in revenue of pi dollars. Professor Gores job is to determine which subareas to hire experts in and which jobs to accept in order to maximize the net revenue, which is the total income from jobs accepted minus the total cost of employing the experts. Consider the following flow network G. It contains a source vertex s, vertices A1; A2;:::;An, vertices J1; J2;:::;Jm, and a sink vertex t. For k D 1; 2 : : : ; n, the flow network contains an edge .s; Ak/ with capacity c.s; Ak/ D ck, and for i D 1; 2; : : : ; m, the flow network contains an edge .Ji;t/ with capacity c.Ji;t/ D pi. For k D 1; 2; : : : ; n and i D 1; 2; : : : ; m, if Ak 2 Ri, then G contains an edge .Ak; Ji/ with capacity c.Ak; Ji/ D 1. a. Show that if Ji 2 T for a finite-capacity cut .S; T / of G, then Ak 2 T for each Ak 2 Ri. b. Show how to determine the maximum net revenue from the capacity of a minimum cut of G and the given pi values. c. Give an efficient algorithm to determine which jobs to accept and which experts to hire. Analyze the running time of your algorithm in terms of m, n, and r D Pm iD1 jRij.

Updating maximum flow Let G D .V; E/ be a flow network with source s, sink t, and integer capacities. Suppose that we are given a maximum flow in G. a. Suppose that we increase the capacity of a single edge .u; / 2 E by 1. Give an O.V C E/-time algorithm to update the maximum flow. b. Suppose that we decrease the capacity of a single edge .u; / 2 E by 1. Give an O.V C E/-time algorithm to update the maximum flow.

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.

The Hopcroft-Karp bipartite matching algorithm In this problem, we describe a faster algorithm, due to Hopcroft and Karp, for finding a maximum matching in a bipartite graph. The algorithm runs in O.pV E/ time. Given an undirected, bipartite graph G D .V; E/, where V D L [ R and all edges have exactly one endpoint in L, let M be a matching in G. We say that a simple path P in G is an augmenting path with respect to M if it starts at an unmatched vertex in L, ends at an unmatched vertex in R, and its edges belong alternately to M and E M. (This definition of an augmenting path is related to, but different from, an augmenting path in a flow network.) In this problem, we treat a path as a sequence of edges, rather than as a sequence of vertices. A shortest augmenting path with respect to a matching M is an augmenting path with a minimum number of edges. Given two sets A and B, the symmetric difference AB is defined as .A B/[ .B A/, that is, the elements that are in exactly one of the two sets. a. Show that if M is a matching and P is an augmenting path with respect to M, then the symmetric difference M P is a matching and jM Pj D jMj C 1. Show that if P1; P2;:::;Pk are vertex-disjoint augmenting paths with respect to M, then the symmetric difference M .P1 [ P2 [[ Pk/ is a matching with cardinality jMj C k. The general structure of our algorithm is the following: HOPCROFT-KARP.G/ 1 M D ; 2 repeat 3 let P D fP1; P2;:::;Pkg be a maximal set of vertex-disjoint shortest augmenting paths with respect to M 4 M D M .P1 [ P2 [[ Pk/ 5 until P == ; 6 return M The remainder of this problem asks you to analyze the number of iterations in the algorithm (that is, the number of iterations in the repeat loop) and to describe an implementation of line 3. b. Given two matchings M and M in G, show that every vertex in the graph G0 D .V; M M / has degree at most 2. Conclude that G0 is a disjoint union of simple paths or cycles. Argue that edges in each such simple path or cycle belong alternately to M or M . Prove that if jMj jM j, then M M contains at least jM j jMj vertex-disjoint augmenting paths with respect to M. Let l be the length of a shortest augmenting path with respect to a matching M, and let P1; P2;:::;Pk be a maximal set of vertex-disjoint augmenting paths of length l with respect to M. Let M0 D M .P1[[Pk/, and suppose that P is a shortest augmenting path with respect to M0 . c. Show that if P is vertex-disjoint from P1; P2;:::;Pk, then P has more than l edges. d. Now suppose that P is not vertex-disjoint from P1; P2;:::;Pk. Let A be the set of edges .M M0 / P. Show that A D .P1 [ P2 [[ Pk/ P and that jAj .k C 1/l. Conclude that P has more than l edges. e. Prove that if a shortest augmenting path with respect to M has l edges, the size of the maximum matching is at most jMj C jV j =.l C 1/. f. Show that the number of repeat loop iterations in the algorithm is at most 2 pjV j. (Hint: By how much can M grow after iteration number pjV j?) g. Give an algorithm that runs in O.E/ time to find a maximal set of vertexdisjoint shortest augmenting paths P1; P2;:::;Pk for a given matching M. Conclude that the total running time of HOPCROFT-KARP is O.pV E/