P31 · 3SAT → 3COLOR

🔊 Listen

1 · 3-COLOR and the gadget reduction

3COLOR = {⟨G⟩ : G is 3-colorable} — assign one of 3 colors to each vertex so no edge has same-colored endpoints. This is NP-complete via a gadget reduction from 3SAT.

Three colors with logical meaning

Label the three colors T (true), F (false), B (base). The construction includes a fixed "palette triangle" so the three colors are globally distinguishable.

Variable gadget

For each variable x_i: a triangle on three nodes (x_i, ¬x_i, B). Three mutually-connected nodes need three different colors; with B fixed to base, x_i and ¬x_i are forced to take T and F (one each). That's the Boolean encoding — colorings ↔ assignments.

OR gadget for clause (a ∨ b ∨ c)

A specific 5-node sub-graph wired so that the gadget is 3-colorable iff at least one of a, b, c is colored T. The wiring forces "if all three inputs are F, no valid coloring exists; otherwise some valid coloring exists."

Combine n variable triangles with m OR gadgets: total O(n + m) nodes, O(n + m) edges. The graph is 3-colorable iff every clause has ≥ 1 true literal iff φ is satisfiable.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

2-COLOR is in P; 3-COLOR is NP-complete. The gap is at exactly 3 — same as SAT vs 2SAT. 2-COLOR = bipartiteness, checkable by BFS.
The OR gadget's structure matters precisely. Off-by-one in the wiring breaks correctness. Sipser gives the exact 6-node gadget; copy it carefully.
Variable triangles share the B vertex. All variable gadgets connect to the same global B (base) node. Failing to share B gives a bad reduction.

🔊 Listen

4 · Q&A defence notes

Q1. Why a triangle for the variable gadget?
Three mutually-adjacent nodes force three different colors. With B fixed to base color, x_i and ¬x_i take T and F in some order — a binary Boolean choice.
Q2. What's the OR-gadget structure?
A 6-node sub-graph (Sipser Figure 7.42) wired so the gadget admits a 3-coloring iff at least one of its three input nodes is colored T. The non-trivial property: if all three inputs are F, the gadget's "output" node must be both T and F simultaneously — impossible.
Q3. Polynomial?
n variable gadgets (3 nodes each, constant) + m OR gadgets (6 nodes each, constant) = O(n + m) nodes. Edges: O(n + m). Linear-size reduction.
Q4. Why does 3-COLOR matter beyond toy graphs?
Real applications: register allocation in compilers (each variable is a vertex, edges between simultaneously-live variables, k registers means k-COLOR). NP-completeness explains why register allocation uses heuristics.

🔊 Listen

5 · Where to read more

Sipser: §7.5, Exercise 7.27 / Karp's original. Lecture notes: Module 5 slide 5. Companion problems: P27 (3SAT → CLIQUE), P28 (CLIQUE → VC).