Knowing how to prove that a problem is NP-complete teaches you to recognize the shared structure of problems that look worlds apart. Here I follow three classic reductions in detail. They start from 3-SAT, a logic problem, and arrive at three graph problems. The pattern learned here is reused almost unchanged in many other proofs.
The problems involved
- 3-SAT: given a formula in conjunctive normal form where every clause has exactly three literals, is there a satisfying assignment?
- Independent set (IS): given a graph G and an integer k, are there k nodes that are pairwise not connected?
- Clique (CLIQUE): given G and k, are there k nodes that are pairwise connected?
- Vertex cover (VC): given G and k, is there a set of k nodes such that every edge has at least one endpoint in the set?
All are in NP: the certificate is the assignment or the set of nodes, and checking it is immediate. It remains to show they are NP-hard.
Reduction 1: from 3-SAT to independent set
Let φ be a formula with m clauses. Build a graph G as follows:
- Clause gadgets: for each clause create three nodes, one per literal, joined to one another in a triangle.
- Conflict edges: join every node labelled x to every node labelled ¬x, whatever clauses they are in.
- Set k = m.
The intuition: choosing a node in a triangle means choosing which literal makes that clause true. Triangles prevent choosing two nodes from the same clause; conflict edges prevent making x and ¬x true together.
Correctness, direction 1. If φ is satisfiable, fix a satisfying assignment. In each clause at least one literal is true: choose one per clause. We get m nodes. They are not in the same triangle, and there are no conflict edges between them, because an assignment does not make both x and ¬x true. It is an independent set of size m.
Correctness, direction 2. If G has an independent set of size m, each triangle contains exactly one of its nodes, because two nodes of the same triangle are connected. Make the corresponding literals true; conflict edges guarantee there are no contradictions; any other variables can be set freely. Every clause has a true literal, so φ is satisfied.
Cost. The graph has 3m nodes and at most O(m²) edges: a polynomial construction.
An example
φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z). Two triangles: {x, y, ¬z} and {¬x, y′, z′}, where the prime marks the second copy. Conflict edges: x with ¬x, ¬z with z′. With k = 2, the set {y, y′} is independent: y and y′ are in different triangles and are not in conflict. It corresponds to the assignment y = true, which satisfies both clauses.
Reduction 2: from independent set to clique
The complement of a graph G, written Ḡ, has the same nodes and an edge between two nodes exactly when G does not.
A set S is independent in G if and only if it is a clique in Ḡ: the pairs not connected in G are all connected in Ḡ. The reduction is therefore:
(G, k) ↦ (Ḡ, k)
Building Ḡ requires examining every pair of nodes, that is O(n²) time. CLIQUE is NP-complete.
Reduction 3: from independent set to vertex cover
Let G be a graph with n nodes. A simple but powerful fact holds:
S is an independent set if and only if V \ S is a vertex cover.
Indeed, if S is independent, no edge has both endpoints in S, so every edge has at least one endpoint outside S, that is in V \ S. The argument reverses without difficulty.
The reduction is:
(G, k) ↦ (G, n − k)
The graph does not even change: only the threshold does. VC is NP-complete.
What these reductions teach
| Reduction | Technique | Idea |
|---|---|---|
| 3-SAT → IS | Gadgets | Triangles for clauses, edges for contradictions |
| IS → CLIQUE | Complement | Missing edges become present ones |
| IS → VC | Duality | A set and its complement swap roles |
Some practical rules I use when building reductions:
- the direction goes from the known problem to the new one;
- every choice in the original problem needs a corresponding gadget;
- consistency constraints, such as "not x and ¬x together", become extra edges, numbers or clauses;
- you must prove both directions of the "if and only if" and check that the construction is polynomial.
Practical consequences
IS, CLIQUE and VC are therefore equivalent for exact polynomial-time solvability, but not for approximation: for vertex cover there is a simple algorithm guaranteeing a solution at most twice the optimum, while for clique nothing comparable is known, and it is known that, if P ≠ NP, approximation is very hard. Polynomial reductions preserve the yes/no answer, not the quality of approximate solutions.
In short
- To prove NP-completeness, show membership in NP and reduce from a known NP-complete problem.
- From 3-SAT to independent set: one triangle per clause and edges between opposite literals, with k equal to the number of clauses.
- Independent set and clique swap by moving to the complement graph.
- S is independent if and only if V \ S is a vertex cover: just change the threshold to n − k.
- Reductions preserve the exact answer, not the quality of approximations.
