CSCI 570 - Summer 2015 - HW 71. A vertex cover of an undirected graph G = (V, E) is a subset of the verticesA ⊆ V such that for every edge e ∈ E, at least one of its incident verticesis in A (that is every edge has at least one of its ends in A). Design analgorithm that takes a bipartite graph G0and a positive integer k, anddecides if G0has a vertex cover of size at most k.Solution: Partition the vertices of the graph into left vertices and rightvertices, that is V = L ∪ R, L ∩ R = ∅ and every edge has one end in Land the other in R.We construct a network¯G0as follows. Add a source s, a sink t and thefollowing edges ; (i) directed edges of capacity 1 from s to every vertex inL , (ii) directed edges of capacity 1 from every vertex in R to t and (iii)make every edge in G0directed from L to R and of infinite capacity.Let (S,¯S) be a cut of¯G0of finite capacity. Without loss of generalityassume that s ∈ S. We claim that we can construct a vertex cover of G0of size equal to the capacity of the cut.Define A := (L − S) ∪ (R ∩ S).Edges that are incident on L−S are covered by L−S. The only edges leftto check are the ones with an end in L ∩ S. The edges that are incidenton L ∩ S have their other end in S and are hence covered by R ∩ S. ThusA is indeed a vertex cover.Edges between L and R have infinite capacity and hence cannot be inthe cut. The only edges crossing the cut are either incident on s or in-cident on t. The number of edges of the form (s, u) where u ∈¯S equals|L − S|. The number of edges of the form (v, t) where v ∈ S is R ∩ S.Hence the size of A equals the capacity of the cut (S,¯S) and our claim istrue.We now claim the converse. That is, given a vertex cover A of G0, wecan construct a cut of¯G0of capacity equal to the size of A.1Define the cut S := {s} ∪ (L − A) ∪ (R ∩ A).For an edge (u, v) ∈ E, if u ∈ S then v ∈ S (since A is a vertex cover).Thus edges in E cannot cross the cut.The number of edges of the form (s, u) where u ∈¯S equals |L ∩ A|. Thenumber of edges of the form (v, t) where v ∈ S equals |R ∩ A|. Hencethe capacity of the cut is |L ∩ A| + |R ∩ A| which is exactly the size of A.Hence, the converse follows.We have thus proven that the size of the min-vertex cover of G0equals thecapacity of the min-cut of¯G0. The capacity of the min-cut of¯G0can becomputed using the Ford-Fulkerson algorithm (say the capacity is m). Ifk < m, output NO, otherwise output YES.2. Given two vertices u and v in a directed graph G = (V, E) and a positiveinteger k, describe an algorithm to decide if there exists k edge disjointpaths from u to v. If the answer to the decision problem is yes, describehow to compute a set of k edge disjoint paths.Solution: See § 7.6 in the textbook.3. Read Chapter 7, Section 7.12 (Baseball Elimination Problem).4. Read Chapter 7, Solved Exercise 2.5. There is a precious diamond that is on display in a museum at m disjointtime intervals. There are n security guards who can be deployed to protectthe precious diamond. Each guard has a list of intervals for which he/sheis available to be deployed. Each guard can be deployed to at most A timeslots and has to be deployed to at least B time slots. Design an algorithmthat decides if there is a deployment of guards to intervals such that eachinterval has either exactly one or exactly two guards deployed.Solution: We create a circulation network as follows. For the ith guardintroduce a vertex giand for the jth time interval introduce a vertex tj.If the ith guard is available for the jth interval, then introduce an edgefrom gito tjof capacity 1. Add a source s and a sink t. To every guardvertex add an edge from s of capacity A and lower bound B. From everyinterval vertex add an edge to t of capacity 2 and lower bound 1. Addan edge from t to s of infinite capacity. We claim that there exists avalid deployment if and only if the above network has a valid circulation.The proof of the claim is virtually identical to the proof in section 7.8of the text for the survey design problem. The algorithm proceeds bydetermining if the network has a circulation (by reducing it to a flowproblem and then applying Ford-Fulkerson) and answers yes if and onlyif there is a circulation. The number of vertices and number of edges inthe resulting flow problem are bounded by O(n) and O(n2) respectively.2The running time of our algorithm is dominated by the flow computationwhich takes O(n3).6. The computer science department course structure is represented as a di-rected acyclic graph G = (V, E) where the vertices correspond to coursesand a directed edge (u, v) ∈ E exists if and only if the course u is a pre-requisite of the course v. By taking a course w ∈ V , you gain a benefitof bwwhich could be a positive or negative number. Design an algorithmthat picks a subset A ⊆ V of courses to take such that the total benefitPw∈Abwis maximized. Remember that if v ∈ A and (u, v) ∈ E, then uhas to be in A. That is, to take a course, you have to take all its prereq-uisites. The running time should be polynomial in |V |.Solution: See solution to project selection problem from section 7.11.7. Solve Kleinberg and Tardos, Chapter 7, Exercise 28.Solution: We create a circulation network as follows. For the ith TAintroduce a vertex piand for the jth time interval introduce a vertex tj.If the ith TA is available for the jth interval, then introduce an edge frompito tjof capacity 1. Add a source s and a sink t. To every TA vertexadd an edge from s of capacity b and lower bound a. From every intervalvertex add an edge to t of capacity 1. Add an edge from t to s of capacityc and lower bound c.We claim that there exists a valid assignment if and only if the abovenetwork has a valid circulation.Proof of Claim: We first show that if there is a valid assignment, thenthe above network has a valid circulation. Assume there is a valid assign-ment. If in the assignment, the ith TA is assigned to the jth interval,then assign a flow of 1 to the edge (pi, tj). Extend this flow to therest of network using flow conservation laws to get a valid flow. That is,the flow on the edge (tj, t) is 1 if a TA is assigned to tjand 0 else, theflow on edge (t, s) is the number of intervals with TAs assigned and (s,pi) is the number of intervals the ith TA is assigned …