CSCI 570 Summer 2015 HW 7 1 A vertex cover of an undirected graph G V E is a subset of the vertices A V such that for every edge e E at least one of its incident vertices is in A that is every edge has at least one of its ends in A Design an algorithm that takes a bipartite graph G0 and a positive integer k and decides if G0 has a vertex cover of size at most k Solution Partition the vertices of the graph into left vertices and right vertices that is V L R L R and every edge has one end in L and the other in R We construct a network G 0 as follows Add a source s a sink t and the following edges i directed edges of capacity 1 from s to every vertex in L ii directed edges of capacity 1 from every vertex in R to t and iii make every edge in G0 directed from L to R and of infinite capacity Let S S be a cut of G 0 of finite capacity Without loss of generality assume that s S We claim that we can construct a vertex cover of G0 of 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 left to check are the ones with an end in L S The edges that are incident on L S have their other end in S and are hence covered by R S Thus A is indeed a vertex cover Edges between L and R have infinite capacity and hence cannot be in the cut The only edges crossing the cut are either incident on s or incident 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 is true We now claim the converse That is given a vertex cover A of G0 we can construct a cut of G 0 of capacity equal to the size of A 1 Define 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 The number of edges of the form v t where v S equals R A Hence the 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 G0 equals the capacity of the min cut of G 0 The capacity of the min cut of G 0 can be computed using the Ford Fulkerson algorithm say the capacity is m If k m output NO otherwise output YES 2 Given two vertices u and v in a directed graph G V E and a positive integer k describe an algorithm to decide if there exists k edge disjoint paths from u to v If the answer to the decision problem is yes describe how 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 disjoint time intervals There are n security guards who can be deployed to protect the precious diamond Each guard has a list of intervals for which he she is available to be deployed Each guard can be deployed to at most A time slots and has to be deployed to at least B time slots Design an algorithm that decides if there is a deployment of guards to intervals such that each interval has either exactly one or exactly two guards deployed Solution We create a circulation network as follows For the ith guard introduce a vertex gi and for the jth time interval introduce a vertex tj If the ith guard is available for the jth interval then introduce an edge from gi to tj of capacity 1 Add a source s and a sink t To every guard vertex add an edge from s of capacity A and lower bound B From every interval vertex add an edge to t of capacity 2 and lower bound 1 Add an edge from t to s of infinite capacity We claim that there exists a valid 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 8 of the text for the survey design problem The algorithm proceeds by determining if the network has a circulation by reducing it to a flow problem and then applying Ford Fulkerson and answers yes if and only if there is a circulation The number of vertices and number of edges in the resulting flow problem are bounded by O n and O n2 respectively 2 The running time of our algorithm is dominated by the flow computation which takes O n3 6 The computer science department course structure is represented as a directed acyclic graph G V E where the vertices correspond to courses and a directed edge u v E exists if and only if the course u is a prerequisite of the course v By taking a course w V you gain a benefit of bw which could be a positive or negative number Design an algorithm that P picks a subset A V of courses to take such that the total benefit w A bw is maximized Remember that if v A and u v E then u has to be in A That is to take a course you have to take all its prerequisites 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 TA introduce a vertex pi and for the jth time interval introduce a vertex tj If the ith TA is available for the jth interval then introduce an edge from pi to tj of capacity 1 Add a source s and a sink t To every TA vertex add an edge from s of capacity b and lower bound a From every interval vertex add an edge to t of capacity 1 Add an edge from t to s of capacity c and lower bound c We claim that there exists a valid assignment if and only if the above network has a valid circulation Proof of Claim We first show that if there is a valid assignment then the above network has a valid circulation Assume there …