4. Let G be a graph. An independent set of G is a set of nodes...

 

Transcribed Image Text:

4. Let G be a graph. An independent set of G is a set of nodes in G such that no two nodes in the set are joined by an edge. Define I = {(G, k) | G has an independent set with k elements }. Show that I is NP-complete as follows: (a) Show that is NP. 1 (b) (c) For a graph G, define G to the complementary graph of G; that is, two nodes u and v are joined by an edge in G if and only if u and v are not joined by an edge in G. Show that for all positive integers k, G has a clique with k elements if and only if G has an independent set with k elements. Using the above result, show that CLIQUE is polynomial-time map- ping reducible to I. 4. Let G be a graph. An independent set of G is a set of nodes in G such that no two nodes in the set are joined by an edge. Define I = {(G, k) | G has an independent set with k elements }. Show that I is NP-complete as follows: (a) Show that is NP. 1 (b) (c) For a graph G, define G to the complementary graph of G; that is, two nodes u and v are joined by an edge in G if and only if u and v are not joined by an edge in G. Show that for all positive integers k, G has a clique with k elements if and only if G has an independent set with k elements. Using the above result, show that CLIQUE is polynomial-time map- ping reducible to I.