graph complement, the other way

CLIQUE ≤p IS

$\mathrm{CLIQUE}\le_p\mathrm{IS}$ — the very same reduction, passing to the complement, works in the reverse direction too.

The construction

On input $\langle H,K\rangle$ with $H=(V,F)$ a graph: return $\langle\bar H,K\rangle$ .

The key to correctness is that complementation is an involution: $\overline{\bar H}=H,\qquad\text{since}\qquad \binom{V}{2}\setminus\left(\binom{V}{2}\setminus F\right)=F .$

Visualization

Original edge (removed)Complement edge (added)

Correctness — both directions

CLIQUE ∈ ⟹ IS ∈

Suppose $\langle H,K\rangle\in\mathrm{CLIQUE}$ , i.e. some $U\subseteq V$ of size $K$ is a clique in $H$ . Let $x,y\in U$ be distinct; then $xy\in F$ , hence $xy\notin\bar F$ , so $U$ is independent in $\bar H$ . Thus $\langle\bar H,K\rangle\in\mathrm{IS}$ .

IS ∈ ⟹ CLIQUE ∈

Suppose $\langle\bar H,K\rangle\in\mathrm{IS}$ , i.e. some $U\subseteq V$ of size $K$ is independent in $\bar H$ . Let $x,y\in U$ be distinct; then $xy\notin\bar F$ , hence $xy\in F$ , so $U$ is a clique in $H$ . Thus $\langle H,K\rangle\in\mathrm{CLIQUE}$ .

Cost of the reduction

TimeO(|V|²) with an adjacency matrix

SpaceO(|V|²)

Output sizeO(|V|²)

Identical to the other direction — it is the same construction.

What it buys

$\mathrm{CLIQUE}\equiv_p\mathrm{IS}$ . This is the cleanest case of two equivalent problems: not merely reductions in both directions, but literally the same function.

Pitfalls

$A\le_p B$ does not imply $B\le_p A$ . Here it happens to hold, thanks to the involution; that is a property of this particular construction, not a general rule.

The chain

Rests on

IS ≤p CLIQUE

Where this was read from

Lesson 7משפט 4: $\mathrm{CLIQUE} \le_p \mathrm{IS}$
2026 '1 מועד 2Polynomial equivalence between the "exactly $k$ ", "at least $k$ ", and "maximum is $k$ " versions of clique.