Recall that, we will look at an alternative proof for NP-completeness of VERTEX-COVER. VERTEX-COVER={{G, k)| G...

Transcribed Image Text:

Recall that, we will look at an alternative proof for NP-completeness of VERTEX-COVER. VERTEX-COVER={{G, k)| G = (V, E) is an undirected graph that has a vertex cover of size k}. A vertex cover is a subset S of V such for each each edge e= (u, v) EE at least one of u, v is in S. a) (3 points) Prove that VERTEX-COVER E NP. b) (7 points) Prove that INDEPENDENT-SET<, VERTEX-COVER. Recall that: INDEPENDENT-SET={(G, i)| G = (V, E) is an undirected graph that has an independent set of size at least i} where an independent set is a subset S of V such that for any pair of vertices u, v E S, (u, v) & E. Recall that, we will look at an alternative proof for NP-completeness of VERTEX-COVER. VERTEX-COVER={{G, k)| G = (V, E) is an undirected graph that has a vertex cover of size k}. A vertex cover is a subset S of V such for each each edge e= (u, v) EE at least one of u, v is in S. a) (3 points) Prove that VERTEX-COVER E NP. b) (7 points) Prove that INDEPENDENT-SET<, VERTEX-COVER. Recall that: INDEPENDENT-SET={(G, i)| G = (V, E) is an undirected graph that has an independent set of size at least i} where an independent set is a subset S of V such that for any pair of vertices u, v E S, (u, v) & E.

Answer rating: 100% (QA)

a To prove that VERTEXCOVER is in NP we need to show that given a graph G and a number k we can veri... View the full answer