Question

Prove that the following problem is NP-complete: given an undirected graph

$G=\left(V,E\right)$and an integer $k$, return a clique of size $k$as well as an independent set of size $k$, provided both exist.

Short answer

Given problem is in NP and NP-Hard. Thus, it is NP-Complete.

Step-by-step solution

Define the problem

Input: A graph$G\left(V,E\right)$ .

Here,V is the set of vertices and E is the set of edges.

Output: A clique and independent set, both of size K , if exist.

To prove: The given problem in NP- complete.

Prove the given problem is NP Complete

To prove that the given problem is in NP, verifier takes the graph G, K and set S and checks that if size of subset S is greater than or equal to and not in. It also checks if every edge of belongs to set E of the graph G.

This is verified in polynomial time. Thus, this problem is in NP.

3-SAT is an NP-complete problem, it is reduced to clique and thus to independent set problem as well.

Step 3:

Consider the example:

$\left(\overline{x}\vee y\vee \overline{z}\right)\left(x\vee \overline{y}\vee z\right)\left(x\vee y\vee z\right)$

In these clauses, see them as the vertices of the graph. Choose one literal from each clause and store that to a set S . The set is the independent set of a graph. Compare if S is equal to K or not. This is done in polynomial time.

Similarly, independent set $\overline{G}$of which is the clique of G is also calculated in polynomial time. Thus, the problem is reducible from 3-SAT, it is proved that it is at least hard as 3-SAT and hence it is in NP-Hard.

Since, given problem is in NP and NP-Hard, it is NP-Complete.