#Notes: Proving CLIQUE-IS problems as NP Complete

Problem : CLIQUE-IS

Statement :

Given an undirected graph G = (V, E) and an integer k, return a clique of size k as well as an independent set of size k, provided both exist.

Reference - DPV 8.14

Solution:

We will try to solve the problem by proving CLIQUE-IS problem as NP Complete in following steps:

1. CLIQUE-IS problem is NP Problem.

   Argument → Lets assume for graph G(V,E) and k, we have given solution as C clique and S as the independent set. We can verify in O(1) that |C| = |S| = k, O(n²) to check each pairs of vertices of C are connected to each other ie edge e = (u,v) and e ∈ E, and O(n²) to check no pair of vertices are connected in given set S ie e’ = (u,v) ∉ E .

2. CLIQUE-IS problem is as hard as CLIQUE problem. We will apply reduction CLIQUE → CLIQUE-IS.

   1. Input to CLIQUE can be converted into input to CLIQUE-IS in polynomial time.

      Argument → CLIQUE takes input graph graph G(V,E) and parameter k. To convert input of CLIQUE into CLIQUE-IS, we will create a graph G’(V’,E) which is a copy of the given graph G(V,E). We also will add a set of S vertices, such that |S| = k to this graph. No new edges are added.

      Thus we will have a graph with all vertices and edges of G(V,E) , and a independent set of vertices S (|S|=k) .

      The new graph G’ can be created in O(|V|+|E|) time and new vertices can be added in O(|S|) time, thus input can be converted in polynomial time.

   2. Solution to CLIQUE-IS problem can be converted to solution for CLIQUE in polynomial time.

      Argument → The solution of the CLIQUE-IS will result in a clique C of size k and set of independent vertices S of size k. This solution can be directly mapped to the solution of CLIQUE problem, which is to find a clique of size ≥ k , as a solution with the clique of size = k is a solution to CLIQUE problem.

      This can be done by dropping the independent vertices of S from the graph G’(V’,E) , thus the result is applicable to the given graph G(V,E). This can be done in O(|S|) time, which is polynomial.

   3. Solution to CLIQUE-IS exists iff solution to CLIQUE problem.

      Argument → From the given graph G(V,E) , we have created graph G’(V’,E) with no new edges. We added only independent set of vertices S to the graph.

      Thus, if there exists a clique C in graph G’(V’,E), it will exist in the given graph G(V,E) as the new added vertices are not connected to any edge, hence are not part of the clique set C. Solution of CLIQUE-IS → CLIQUE

      Also, if there does not exists a clique in graph G’(V’,E), there cannot exist a clique in the given graph G(V,E) as the edges in both graphs are the same and no new vertices are connected. Thus !CLIQUE-IS → !CLIQUE.

      Thus, Solution to CLIQUE-IS exists iff solution to CLIQUE problem.

Thus CLIQUE-IS is a NP Complete problem.