testions 1 In this problem, we will define the Set Cover problem and show that it...

  

Transcribed Image Text:

testions 1 In this problem, we will define the Set Cover problem and show that it is NP-complete. (a) (5 points) Suppose I gave you some set U = {1,2,3,4,5) of elements and some subset of U's power set S = {{1,2,3), (2,4), (3, 4), (4,5). Is there a way to choose at most 1 set in S that covers all of U? How about if I let you pick 2 sets? 3? NO Yes If allured to pick 2 sets {{123}, {4,5}} (b) (5 points) Show that SETCOVER = {(U, S,k) | SCP(U) and there is some subset TCS of size k that covers all of U) E NP. You may pick whichever definition of NP you prefer. (c) (10 points) Show that VERTEXCOVER Sp SETCOVER. That is, given some graph G and integer k, we need to construct some U and S and k' such that (G,k) E VERTEXCOVER (U,S,K) E SETCOVER, and this construction is limited to a polynomial amount of time in (G, k)|. testions 1 In this problem, we will define the Set Cover problem and show that it is NP-complete. (a) (5 points) Suppose I gave you some set U = {1,2,3,4,5) of elements and some subset of U's power set S = {{1,2,3), (2,4), (3, 4), (4,5). Is there a way to choose at most 1 set in S that covers all of U? How about if I let you pick 2 sets? 3? NO Yes If allured to pick 2 sets {{123}, {4,5}} (b) (5 points) Show that SETCOVER = {(U, S,k) | SCP(U) and there is some subset TCS of size k that covers all of U) E NP. You may pick whichever definition of NP you prefer. (c) (10 points) Show that VERTEXCOVER Sp SETCOVER. That is, given some graph G and integer k, we need to construct some U and S and k' such that (G,k) E VERTEXCOVER (U,S,K) E SETCOVER, and this construction is limited to a polynomial amount of time in (G, k)|.