Answer Happy

Question 6 What is the Vertex-Cover problem? Does P = NP? For a given set of Vertices can the answer be checked in P or NP time? What data structure could we use for E'? Is there anyway we can organize E' better to make line 6 faster? What was the importance of showing how a solution to Vertex Cover could be used to solve the Clique problem? What is the complement of a graph? Can we use Approx-Vertex-Cover to find a Vertex Cover of a specific size? What would it mean if we could use Approx-Vertex-Cover to find a Vertex Cover of a specific size? APPROX-VERTEX-COVER (G) 1 C = 0 2 E' = G.E 3 while E' 0 4 let (u, v) be an arbitrary edge of E' C = CU{u, v} remove from E' every edge incident on either u or v 567 6 7 return C