Reduce Independent Set to Clique

Turn an independent-set instance into a clique instance by complementing the edge set.

Problem

Given an undirected graph $G=(V,E)$ and integer $k$, construct in polynomial time a graph $G'$ and integer $k'$ such that $G$ has an independent set of size $k$ if and only if $G'$ has a clique of size $k'$. Prove both directions and argue that the construction is polynomial in the encoded input length.

Hint 1

The same vertex set can serve both instances. What edge relation turns non-adjacency into adjacency?

Hint 2

The parameter need not change if the vertex set is unchanged.

Full solution

Let $G'=\overline{G}=(V,\binom{V}{2}\setminus E)$ be the complement graph on the same vertex set, and set $k'=k$. Listing all non-edges of $G$ takes $O(|V|^2)$ time, which is polynomial in the standard adjacency-matrix or adjacency-list encoding.

A set $S\subseteq V$ is independent in $G$ exactly when no two vertices of $S$ are joined by an edge of $E$. Equivalently, every pair of distinct vertices in $S$ is joined by an edge of $\overline{G}$. Therefore $S$ is a clique in $G'$. The converse is identical: a clique in $\overline{G}$ has no $G$-edge inside it, so it is independent in $G$. Taking $|S|=k$ yields the iff.

Membership of CLIQUE in NP is standard: a candidate vertex set of size $k$ is a certificate, and every pair can be checked for an edge in polynomial time. Combined with the NP-completeness of Independent Set (via 3SAT), this reduction proves NP-completeness of CLIQUE.

Checkpoint

Distinguish graph complement (flip edges, keep $k$) from vertex-set complement (used for Vertex Cover, which changes the parameter).

Common mistakes

• Changing $k$ unnecessarily, or forgetting that loops and self-pairs are never edges.
• Building the complement incorrectly by deleting vertices instead of flipping edges.
• Proving only one direction of the equivalence.

Provenance note

This is an independently written presentation of a standard identity used throughout the course reduction atlas. It is textbook-aligned (Sipser / Garey–Johnson) and reflected in course lecture notes on IS, CLIQUE, and VC; it is not a verbatim assignment transcript.

Sources and verification

• Merged summary, pp. 55-57
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT19 and GT20
• Catalog mapping: data/exercises.json; statements and solutions are independently written.

Open in the visualization gallery: Independent Set → Clique