CLIQUE = {⟨G, k⟩ : G has a complete subgraph on k vertices}. We show it is NP-complete by
reducing 3SAT to it. The reduction is purely combinatorial.
Reduction · φ ∈ 3SAT ⇔ (Gφ, m) ∈ CLIQUE
Given a 3CNF formula φ with m clauses:
Nodes: one per literal-occurrence (3 per clause; 3m nodes total).
Edges: between two nodes iff they are in different clauses AND their literals are not negations of each other.
Witness: a clique of size m corresponds to one literal per clause, all simultaneously truth-able. That's exactly a satisfying assignment.
The reduction is polynomial: Gφ has 3m nodes and ≤ 9m² edges. Construction is straightforward. Correctness:
φ is satisfiable ⇒ pick a true literal in each clause ⇒ those m nodes form a clique. Conversely a clique of size m must
pick one node per cluster (no intra-cluster edges) and the pairwise compatibility means the chosen literals can all be set true.
🔊 Listen
2 · The construction as a picture
🔊 Listen
3 · Animated demo · auto-plays · loops
Build the graph Gφ, find the 3-clique Auto-plays
🔊 Listen
3 · Q&A defence notes
Q1. Why no edges within a clause's cluster?
Because a satisfying assignment makes one literal per clause true. We don't need (and can't use) two literals from the same clause. Removing intra-cluster edges forces the clique to pick exactly one per cluster.
Q2. Why "not negations" between clusters?
If two nodes are x and ¬x, no consistent assignment makes both true. Excluding them from the edge set prevents a clique from picking incompatible literals.
Q3. What if the formula has clauses with fewer than 3 literals?
The reduction also handles 2-literal and 1-literal clauses (just smaller clusters). For 3SAT specifically we always have 3 literals per clause.
Q4. Why does this prove CLIQUE is NP-complete?
Two parts: (a) CLIQUE ∈ NP (the clique itself is a polynomial-size witness). (b) 3SAT ≤p CLIQUE (this reduction). 3SAT is NP-complete, so CLIQUE is too.
Q5. Polynomial bound on the reduction size?
3m nodes, ≤ (3m choose 2) ≈ O(m²) edges. Construction takes O(m²) time. Polynomial in the formula size.
🔊 Listen
4 · Pitfalls
The clique size is m (number of clauses), not n (variables). The k value passed to the CLIQUE problem is exactly the number of clauses in φ. Easy mistake: setting k = n.
Same variable in different clauses = different nodes. Each literal-occurrence gets its own node. Even if x appears in three clauses, that's three nodes.
Edges encode compatibility, not truth. The graph doesn't know what's true. It only says "these two literals could both be true under some assignment." Find a clique to pick m mutually-compatible literals.
The reduction goes only one way. 3SAT ≤p CLIQUE. Going the other way (CLIQUE ≤p 3SAT) needs a different construction.