11.17

Membership in NP. A certificate consists of two vertex sets [math]C,T\subseteq V(G)[/math], each of size [math]k[/math]. In O(k2) time we check that every pair in [math]C[/math] is joined by an edge (clique) and every pair in [math]T[/math] is non-adjacent (independent set). Hence the problem is in NP.

NP-hardness (reduction from CLIQUE).
Given an instance [math](H,k)[/math] of the classical CLIQUE problem, build

[math]G = H \;\cup\; I_k[/math],

where [math]I_k[/math] is a set of [math]k[/math] new vertices with no edges, and no edges are added between [math]H[/math] and [math]I_k[/math]. This construction is clearly computable in polynomial time and keeps the same parameter [math]k[/math].

• If [math]H[/math] has a clique of size [math]k[/math], that clique is still present in [math]G[/math]; together with the [math]k[/math] isolated vertices it gives the required independent set.
• Conversely, if [math]G[/math] contains both a clique and an independent set of size [math]k[/math], the independent set can only be the [math]k[/math] isolated vertices (any other vertex is adjacent to something in that set), so the clique must lie entirely inside [math]H[/math]. Thus [math]H[/math] has a [math]k[/math]-clique.

Therefore

[math](H,k)\;\in\;\text{CLIQUE}\ \Longleftrightarrow\ (G,k)\;\in\;\text{Clique, no-clique}[/math]

and our problem is NP-hard.

Conclusion. The decision problem “Clique, no-clique” is in NP and NP-hard, hence NP-complete.

Back to Chapter 11