Homework answers / question archive / In the independent set problem (LS)

In the independent set problem (LS)

Computer Science

Share With

In the independent set problem (LS). we are given a graph with n. vertices and m edges. "7e want to decide if there are 1.: vertices in the graph in which no two of them are connected by an edge. For this question. assume that LS is NP—Cornplete. A clique is a graph in which there is an edge between every pair of vertices (i.e., a complete graph). Consider the clique problem (Clique): given a graph. decide if there is a clique of size A: in that graph. Show that Clique is in NP. Then. show that Clique is N P—Cornplete by reducing LS to Clique.

Please provide runtime of algorithm