A graph G has an independent set of size k if there is a set V of k nodes in G so that no two nodes in V share anedge. Let INDEPENDENT-SET = { | G is a graph with an independent set of size k }.%3DShow that INDEPENDENT-SET e NP by writing either a verifier or an NDTM.Show that INDEPENDENT-SET is NP-complete by reduction from VERTEX-COVER.

Given- A graph with an independent set of size k such that if there is a V of 'k' nodes in G, so that no two nodes in V share an edge. i.e.INDEPENDENT-SET=G,kG is a graph with an independent set of size k to show that --INDEPENDENT-SET∈ NP by writing either a verifier oe an NDTM.-INDEPENDENT-SET is NP - complete by reduction from VERTEX-COVER Independent Set is NPIf any problem is in NP, then, given a ‘certificate’, which is a solution to the problem and an instance of the problem (a graph G and a positive integer k, in this case), we will be able to verify (check whether the solution given is correct or not) the certificate in polynomial time.The certificate is a subset V’ of the vertices, which comprises the vertices belonging to the independent set. We can validate this solution by checking that each pair of vertices belonging to the solution are non-adjacent, by simply verifying that they don’t share an edge with each other. This can be done in polynomial time, that is O(V +E) using the following strategy of graph G(V, E): Independent Set is NP-Hard.In order to prove that the Independent Set problem is NP-Hard, we will perform a reduction from a known NP-Hard problem to this problem. We will carry out a reduction from which the Clique Problem can be reduced to the Independent Set problem.Every instance of the clique problem consisting of the graph G (V, E) and an integer k can be converted to the required graph G’ (V’, E’) and k’ of the Independent Set problem. We will construct the graph G’ in the following way: V’ = V i.e. all the vertices of graph G are a part of the graph G’E’ = complement of the edges E, i.e. the edges not present in the original graph G. The graph G’ is the complementary graph of G. The time required to compute the complementary graph G’ requires a traversal over all the vertices and edges. The time complexity of this is O (V+E).We will now prove that the problem of computing the independent set indeed boils down to the computation of the clique. The reduction can be proved by the following two propositions: assuming that the graph G contains a clique of size k. The presence of clique implies that there are k vertices in G, where each of the vertices is connected by an edge with the remaining vertices. This further shows that since these edges are contained in G, therefore they can’t be present in G’. As a result, these k vertices are not adjacent to each other in G’ and hence form an Independent Set of size k. Assuming that the complementary graph G’ has an independent set of vertices of size k’. None of these vertices shares an edge with any other vertices. When we complement the graph to obtain G, these k vertices will share an edge and hence, become adjacent to each other. Therefore, the graph G will have a clique of size k. Thus, we can say that there is an independent set of size k in graph G if there is a clique of size k in G’ (complement graph). Therefore, any instance of the independent set problem can be reduced to an instance of the clique problem. Thus, the independent set is NP-Hard.