Alice, Bob and you have been studying graph algorithms. You understand the reduction between Independent Set...

  

Transcribed Image Text:

Alice, Bob and you have been studying graph algorithms. You understand the reduction between Independent Set and Clique quite well but are now considering another of Karp's 21 Problems. A vertex cover is a set of vertices in a graph such that every edge in the graph has at least one end point in the set. That is, no edge is left uncovered with both of its endpoints not in the set. Vertex Cover (VC) Input: G= (V,E) a undirected graph and k0. Output: "yes" if there exists a set of vertices V' of size k such that every edge has at least one endpoint in V', "no" otherwise. a) (2 points) What is the size of the smallest vertex cover on this graph? b) (2 points) You want to show that Vertex Cover is in NP so you will create a verifica- tion algorithm. What type of proof would you accept to convince you that there is a vertex cover of size k? c) (3 points) Give pseudocode for a verification procedure for Vertex Cover. d) (3 points) Argue your verification procedure is correct for Vertex Cover. e) (5 points) Show that Vertex Cover is NP-complete by reducing one of Clique or Independent Set to Vertex Cover. That is, show that A p Vertex Cover for your choice of problem A. Alice, Bob and you have been studying graph algorithms. You understand the reduction between Independent Set and Clique quite well but are now considering another of Karp's 21 Problems. A vertex cover is a set of vertices in a graph such that every edge in the graph has at least one end point in the set. That is, no edge is left uncovered with both of its endpoints not in the set. Vertex Cover (VC) Input: G= (V,E) a undirected graph and k0. Output: "yes" if there exists a set of vertices V' of size k such that every edge has at least one endpoint in V', "no" otherwise. a) (2 points) What is the size of the smallest vertex cover on this graph? b) (2 points) You want to show that Vertex Cover is in NP so you will create a verifica- tion algorithm. What type of proof would you accept to convince you that there is a vertex cover of size k? c) (3 points) Give pseudocode for a verification procedure for Vertex Cover. d) (3 points) Argue your verification procedure is correct for Vertex Cover. e) (5 points) Show that Vertex Cover is NP-complete by reducing one of Clique or Independent Set to Vertex Cover. That is, show that A p Vertex Cover for your choice of problem A.