IS ≤p CLIQUE

The construction

On input $\langle G,K\rangle$ with $G=(V,E)$ and $K\in\mathbb{N}$ :

Build the complement graph $\bar G=(V,\bar E)$ , where $\bar E=\Big\{xy\ \Big|\ x,y\in V,\ x\ne y\Big\}\setminus E=\binom{V}{2}\setminus E .$
Return $\langle\bar G,K\rangle$ .

The number $K$ is untouched; only the graph flips.

Visualization

Original edge (removed)Complement edge (added)

Correctness — both directions

IS ∈ ⟹ CLIQUE ∈

Suppose $\langle G,K\rangle\in\mathrm{IS}$ . Then some $U\subseteq V$ with $|U|=K$ is independent in $G$ .

Consider the same $U$ inside $\bar G$ — legitimate, since both graphs share the vertex set $V$ . Then $U\subseteq V$ and $|U|=K$ . It remains to show $U$ is a clique in $\bar G$ : let $x,y\in U$ be distinct. Since $U$ is independent in $G$ we have $xy\notin E$ , and by definition of the complement every non-edge of $E$ on distinct vertices is an edge of $\bar E$ ; so $xy\in\bar E$ . Hence $U$ is a clique in $\bar G$ , i.e. $\langle\bar G,K\rangle\in\mathrm{CLIQUE}$ .

CLIQUE ∈ ⟹ IS ∈

Suppose $\langle\bar G,K\rangle\in\mathrm{CLIQUE}$ . Then some $U\subseteq V$ with $|U|=K$ is a clique in $\bar G$ (naming the graph is mandatory — there are two of them here).

Consider the same $U$ inside $G$ . Then $U\subseteq V$ and $|U|=K$ . Let $x,y\in U$ be distinct. Since $U$ is a clique in $\bar G$ , $xy\in\bar E$ , and by definition of the complement $xy\notin E$ . Hence $U$ is independent in $G$ , i.e. $\langle G,K\rangle\in\mathrm{IS}$ .

Cost of the reduction

TimeO(|V|²) with an adjacency matrix

SpaceO(|V|²)

Output sizeO(|V|²)

With an adjacency matrix, testing "is $xy\in E$ " costs $O(1)$ , so scanning all $\binom{|V|}{2}$ pairs costs $O(|V|^2)$ . With an edge list, rescanning per pair gives $O(|V|^2\cdot|E|)$ . Both are polynomial, so for the claim there is no difference — which is exactly why implementation detail may be treated loosely here.

What it buys

$\mathrm{IS}$ is no harder than $\mathrm{CLIQUE}$ . With the converse reduction the two problems are equivalent under $\le_p$ : one is in $\mathrm P$ iff the other is, and one is NP-complete iff the other is.

Pitfalls

"Delete the clique's edges" — rejected at once: the reduction cannot find a clique, and the whole point is that we cannot solve the problem. The same trap appears in computability: a reduction from $\mathrm{HALT}$ cannot test whether its input is in the language.
"Delete every edge" — the output is then never in $\mathrm{CLIQUE}$ (for $K\ge2$ ), whatever the input; that kills the "if" direction. "Add every edge" — the output is then always in $\mathrm{CLIQUE}$ ; that kills the other. Any operation producing a predetermined output breaks one direction, so the operation must swap, not flatten.

The construction

Visualization

Independent Set → Clique