Scope note. This year, space complexity (PSPACE, NPSPACE, Savitch's theorem, coNP, TQBF, the full hierarchy L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME) is not exam material. The course ends at NP-completeness reductions. This page covers everything that is examinable from Week 8.
The Big Picture
On the previous page, we built the entire framework: P, NP, polynomial-time reductions, NP-completeness, and the Cook-Levin theorem (SAT is NPC). We ended with the two-step recipe for proving a problem NP-complete:
- Show it's in NP — give a polynomial-time verifier (or NDTM).
- Show it's NP-hard — reduce a known NPC problem to it.
This page is where we use that recipe. We'll prove three problems NP-complete by building explicit Karp reductions, each one building on the last:
Cook-Levin: every NP problem \(\leq_p\) SAT \(\leq_p\) 3SAT \(\leq_p\) VERTEX COVER \(\leq_p\) CLIQUE
HAMC (NPC by intimidation) \(\leq_p\) HAMP
Each reduction is a translation function that converts instances of one problem into instances of another, preserving yes/no answers in both directions. The constructions range from intricate (3-SAT to VC — builds a graph with three kinds of edges) to elegant (VC to Clique — just flip the edges).
The SWE analogy. Think of each reduction as a compiler. 3-SAT instances are "source code" in one language; the reduction "compiles" them into Vertex Cover instances in another language. The compilation must preserve meaning: satisfiable formulas become graphs with small covers, unsatisfiable formulas become graphs that need too many vertices. If your compiler ever turns a buggy program into a correct one (or vice versa), the compiler is broken.
Exam expectation. You will not be asked to construct reductions from scratch. Instead, given a reduction, you should be able to: (1) apply it to a specific instance, (2) critique a proof of correctness, and (3) fix mistakes in broken reductions. So focus on understanding why each construction works, not memorizing it.
Warm-Up: NPC Reasoning
Before diving into constructions, let's sharpen our intuition about what NPC means with a reasoning exercise.
Exercise — True or False?
Consider three problems A, B, C such that: \(A \leq_p B\) and \(B \leq_p A\), with \(A \in \text{NPC}\), \(B \in \text{NP}\), \(C \in \text{P}\).
Which of these is false?
- It is not possible for \(B\) to be \(\Sigma^*\).
- \(B\) is NP-Complete.
- \(C \leq_p B\).
- If \(P = NP\) then \(A \leq_p C\) must hold.
Answer: D is false. Let's see why each works:
- A is TRUE. If \(B = \Sigma^*\), then \(A \leq_p \Sigma^*\) means A is trivially decidable (every input maps to "yes"). But A is NP-complete, so every NP problem reduces to A. If A is trivial, SAT reduces to it, making SAT trivial, implying P = NP. Since we don't assume P = NP, B cannot be \(\Sigma^*\).
- B is TRUE. Since \(A \leq_p B\) and A is NP-hard, every NP problem reduces to A, which reduces to B. So B is NP-hard. Combined with \(B \in \text{NP}\), B is NPC.
- C is TRUE. Since B is NPC, it's nontrivial (has both yes- and no-instances). For any \(C \in P\): solve C in poly time; if yes, output a known yes-instance of B; if no, output a known no-instance. That's a valid Karp reduction.
- D is FALSE. Even if P = NP, the problem C could be \(\emptyset\) (rejects everything). Then \(A \leq_p \emptyset\) requires every no-instance of A to map into \(\emptyset\) — but \(\emptyset\) has no yes-instances, so A would need to be empty too. Since A is NPC (nonempty), this fails. Concrete example: \(C = \emptyset\), \(A = \text{SAT}\). Even with P = NP, SAT cannot reduce to the empty language.
The Wikipedia diagram subtlety. The famous Euler diagram showing P, NP, NPC, and NP-hard has a footnote: \(\emptyset\) and \(\Sigma^*\) are in P but are not NP-complete. No NP problem can meaningfully reduce to them because reductions need both yes- and no-instances to land correctly. NPC problems must be nontrivial.
3-SAT \(\leq_p\) Vertex Cover
This is the big one — the most complex reduction in the course. It takes a 3-SAT formula and builds a graph where small vertex covers correspond exactly to satisfying assignments. The construction has three types of edges, each encoding a different aspect of the formula.
What is Vertex Cover?
VERTEX COVER (VC).
Instance: A graph \(G = (V, E)\) and a positive integer \(K\).
Question: Is there a subset \(V' \subseteq V\) with \(|V'| \leq K\) such that every edge has at least one endpoint in \(V'\)?
Real-world version: You're placing security cameras at intersections in a city. Each camera covers all roads meeting at its intersection. Can you cover every road with at most \(K\) cameras? That's Vertex Cover.
Step 1: VC is in NP
Before proving NP-hardness, we need VC in NP. This is the easy part — given a proposed cover, we just check it:
VC ∈ NP — Polynomial-time verifier
def verify_vc(g: Graph, k: int, sol: Set[Node]) -> bool:
if len(sol) > k:
return False
for e in g.all_edges():
if e.a not in sol and e.b not in sol:
return False
for s in sol:
if s not in g.all_nodes():
return False
return True
Certificate: The set \(V'\) (the proposed vertex cover). Size: at most \(|V|\) — polynomial.
Running time: \(O(|V'| + |E| \cdot |V'| + |V'| \cdot |V|)\) — polynomial in the input size.
Step 2: VC is NP-Hard — The Reduction from 3-SAT
Given a 3-SAT instance \(I = (U, C)\) with variables \(U\) and clauses \(C\), we construct a graph \(f(I) = (V, E, K)\) in three stages. Follow along with paper — this is best learned by drawing.
Construction Step 1: Proposition Edges
For every variable \(u \in U\), create two nodes \(u\) and \(\neg u\), connected by a single edge \(\{u, \neg u\}\).
What this encodes: Any vertex cover must include at least one endpoint of each edge. So for each variable, the cover must "choose" either \(u\) or \(\neg u\) — exactly like choosing TRUE or FALSE. One node per variable is forced into the cover.
Construction Step 2: Clause Triangles
For every clause \(c_j = \{x_1, x_2, x_3\}\) in \(C\), create three new nodes \(x_{j,1}, x_{j,2}, x_{j,3}\) and connect them into a triangle (all three edges).
What this encodes: A triangle has 3 edges. A single vertex covers at most 2 of them. So any vertex cover needs at least 2 of the 3 triangle nodes. This means exactly one node per triangle can be "left out" of the cover — this will correspond to the literal that satisfies the clause.
Construction Step 3: Connection Edges
For each clause-triangle node \(x_{j,k}\), add an edge connecting it to the corresponding literal node from the proposition edges. If \(x_{j,k}\) represents the literal \(\ell\) in clause \(j\), add edge \(\{x_{j,k}, \ell\}\).
What this encodes: This bridges the "variable choice" (proposition edges) with the "clause satisfaction" (triangles). The excluded triangle node's connection edge must still be covered — and it will be covered from the proposition side, but only if that literal was set to TRUE.
Construction Step 4: Set K
$$K = |U| + 2|C|$$
Exactly 1 node per proposition edge + 2 nodes per clause triangle. This is the minimum possible cover size for this graph structure — any valid cover of size \(\leq K\) must be exactly \(K\), with zero slack.
Why the tight budget matters. Since the minimum cover is exactly \(K\), a cover of size \(\leq K\) must use exactly 1 node per proposition edge and exactly 2 nodes per clause triangle. No slack means the cover structure perfectly mirrors a truth assignment. This tightness is what makes the proof work in both directions.
Worked Example
3-SAT instance: \(U = \{x, y, z\}\), \(C = \{(\neg x \lor y \lor \neg z),\; (x \lor y \lor \neg z)\}\)
Step 1 — Proposition edges (one per variable):
- Variable \(x\): nodes \(x\) and \(\neg x\), edge \(\{x, \neg x\}\)
- Variable \(y\): nodes \(y\) and \(\neg y\), edge \(\{y, \neg y\}\)
- Variable \(z\): nodes \(z\) and \(\neg z\), edge \(\{z, \neg z\}\)
Step 2 — Clause triangles (one per clause):
- Clause 1 = \((\neg x, y, \neg z)\): nodes \(x_{1,1}, x_{1,2}, x_{1,3}\) forming a triangle
- Clause 2 = \((x, y, \neg z)\): nodes \(x_{2,1}, x_{2,2}, x_{2,3}\) forming a triangle
Step 3 — Connection edges (clause nodes to their literal nodes):
- \(\{x_{1,1}, \neg x\}\), \(\{x_{1,2}, y\}\), \(\{x_{1,3}, \neg z\}\)
- \(\{x_{2,1}, x\}\), \(\{x_{2,2}, y\}\), \(\{x_{2,3}, \neg z\}\)
Step 4: \(K = 3 + 2(2) = 7\).
Total: 12 nodes, 15 edges, \(K = 7\).
Verification — truth assignment \(\tau\): \(x = 0, y = 1, z = 0\)
True literals: \(\neg x, y, \neg z\). Include these 3 proposition nodes in \(V'\).
Clause 1 \(= (\neg x, y, \neg z)\): satisfied by \(\neg x\) (first literal). Exclude \(x_{1,1}\), include \(x_{1,2}\) and \(x_{1,3}\).
Clause 2 \(= (x, y, \neg z)\): satisfied by \(y\) (second literal). Exclude \(x_{2,2}\), include \(x_{2,1}\) and \(x_{2,3}\).
\(V' = \{\neg x, y, \neg z, x_{1,2}, x_{1,3}, x_{2,1}, x_{2,3}\}\). Size = 7 = \(K\).
Check: every edge has at least one endpoint in \(V'\)? Yes — proposition edges covered by the true literal, triangle edges covered by the 2 included nodes, connection edges covered from either side.
Verification — truth assignment \(\tau\): \(x = 1, y = 0, z = 0\)
True literals: \(x, \neg y, \neg z\). Include these 3 proposition nodes in \(V'\).
Clause 1 \(= (\neg x, y, \neg z)\): satisfied by \(\neg z\) (third literal). Exclude \(x_{1,3}\), include \(x_{1,1}\) and \(x_{1,2}\).
Clause 2 \(= (x, y, \neg z)\): satisfied by \(x\) (first literal). Exclude \(x_{2,1}\), include \(x_{2,2}\) and \(x_{2,3}\).
\(V' = \{x, \neg y, \neg z, x_{1,1}, x_{1,2}, x_{2,2}, x_{2,3}\}\). Size = 7 = \(K\). All edges covered.
Soundness: Both Directions
A valid reduction must preserve answers in both directions. "Satisfiable implies coverable" (forward) AND "coverable implies satisfiable" (backward). Let's prove both.
Forward: \(I \in \text{3-SAT} \implies f(I) \in \text{VC}\)
Assume \(I\) is satisfiable. Let \(\tau\) be a satisfying assignment.
- For each variable \(u\), include the TRUE literal node in \(V'\). (\(|U|\) nodes.)
- For each clause \(c_j\): at least one literal is true under \(\tau\). Pick one. Include the other two clause-triangle nodes in \(V'\). (\(2|C|\) nodes.)
- Total \(|V'| = |U| + 2|C| = K\).
All edges covered:
- Proposition edges: Each \(\{u, \neg u\}\) has exactly one endpoint in \(V'\) (the TRUE literal).
- Triangle edges: 2 of 3 nodes in each triangle are in \(V'\). A triangle with 2 nodes has all 3 edges covered (the 2 nodes share one edge, and each covers one edge to the excluded node).
- Connection edges: The 2 included triangle nodes cover their connection edges directly. The excluded triangle node \(x_{j,k}\) represents the literal that was TRUE — its connection edge goes to the TRUE literal's proposition node, which IS in \(V'\). Covered from the proposition side.
So \(V'\) is a vertex cover of size \(K\). Therefore \(f(I) \in \text{VC}\). \(\square\)
Backward: \(f(I) \in \text{VC} \implies I \in \text{3-SAT}\)
Assume \(f(I)\) has a vertex cover \(V'\) with \(|V'| \leq K\).
- The minimum cover size is \(|U| + 2|C| = K\) (each proposition edge needs \(\geq 1\) node, each triangle needs \(\geq 2\)). So \(|V'| = K\) exactly.
- The cover uses exactly 1 node per proposition edge and exactly 2 per triangle. (Any deviation — e.g., 0 from some proposition edge — would require compensating elsewhere, exceeding \(K\).)
- Define truth assignment \(\tau\): if node \(u\) is in \(V'\), set \(u = \text{TRUE}\); if \(\neg u\) is in \(V'\), set \(u = \text{FALSE}\). (Well-defined because exactly one of \(\{u, \neg u\}\) is in \(V'\).)
- For each clause \(c_j\): exactly 1 triangle node is NOT in \(V'\). Call it \(x_{j,k}\). Its connection edge \(\{x_{j,k}, \ell\}\) must be covered. Since \(x_{j,k} \notin V'\), the literal node \(\ell\) must be in \(V'\). So \(\ell\) is TRUE under \(\tau\), meaning clause \(c_j\) is satisfied.
- Every clause has at least one true literal. So \(\tau\) satisfies \(C\), and \(I \in \text{3-SAT}\). \(\square\)
Polynomiality
| Step |
Operation |
Time |
| 1 |
Add 2 nodes + 1 edge per variable |
\(O(|U|)\) |
| 2 |
Add 3 nodes + 3 edges per clause |
\(O(|C|)\) |
| 3 |
Connect clause nodes to literal nodes |
\(O(|C| \times |U|)\) |
| 4 |
Compute \(K = 2|C| + |U|\) |
\(O(1)\) |
Total: \(O(|C| \times |U|)\) — clearly polynomial.
Conclusion. VC ∈ NP (polynomial verifier) + VC is NP-Hard (3-SAT \(\leq_p\) VC) = VC is NP-Complete.
Vertex Cover \(\leq_p\) Clique
After the complexity of 3-SAT \(\leq_p\) VC, this reduction is refreshingly simple. The trick: flip all the edges.
What is Clique?
CLIQUE.
Instance: A graph \(G = (V, E)\) and an integer \(K\).
Question: Is there a subset \(V' \subseteq V\) with \(|V'| \geq K\) such that every pair of vertices in \(V'\) is connected by an edge? (A complete subgraph of size \(\geq K\).)
Real-world version: In a social network, a clique is a group where everyone is mutual friends with everyone else. Can you find such a group of at least \(K\) people?
Step 1: Clique is in NP
CLIQUE ∈ NP
Certificate: A set of vertices \(V'\) with \(|V'| \geq K\).
Verifier: Check \(|V'| \geq K\). Then for each pair \(u, v \in V'\) with \(u \neq v\), check that \(\{u,v\} \in E\). Takes \(O(K^2) \leq O(|V|^2)\) — polynomial.
Step 2: The Complement Graph Reduction
The reduction. Given a VC instance \(I = (V, E, K)\), produce the CLIQUE instance:
$$f(I) = (V, E^c, |V| - K)$$
where \(E^c = \{\{u,v\} \mid u, v \in V,\; u \neq v,\; \{u,v\} \notin E\}\) is the complement of the edge set.
That's it. Same vertices. Flip which pairs are connected. Change "at most \(K\)" to "at least \(|V| - K\)."
Why It Works
The core insight: if \(V'\) is a vertex cover of size \(K\) in \(G\), then \(V \setminus V'\) (the remaining \(|V| - K\) vertices) form a clique in \(G^c\). Here's why:
- \(V'\) covers every edge in \(E\) — every edge has at least one endpoint in \(V'\).
- So for any two vertices \(u, v\) that are both outside \(V'\) (both in \(V \setminus V'\)): there is no edge \(\{u,v\}\) in \(E\). (If there were, \(V'\) wouldn't cover it.)
- No edge in \(E\) between them means there is an edge in \(E^c\) between them.
- Every pair in \(V \setminus V'\) is connected in \(G^c\) — that's a clique of size \(|V| - K\).
The converse is symmetric: a clique of size \(|V| - K\) in \(G^c\) means the remaining \(K\) vertices form a vertex cover in \(G\).
Worked Example
Applying the reduction
VC instance: \(G\) with \(V = \{1, 2, 3, 4, 5\}\), edges \(\{1\text{-}2, 2\text{-}3, 3\text{-}4, 4\text{-}5, 5\text{-}1, 1\text{-}3\}\), \(K = 3\).
Complement graph \(G^c\): edges between pairs NOT connected in \(G\): \(\{1\text{-}4, 2\text{-}4, 2\text{-}5, 3\text{-}5\}\).
Target clique size: \(K' = |V| - K = 5 - 3 = 2\).
Does \(G^c\) have a clique of size \(\geq 2\)? Yes — \(\{2, 5\}\) is connected in \(G^c\) (edge \(\{2,5\}\) exists). Also \(\{2,4\}\), \(\{3,5\}\), etc.
This corresponds to: \(V \setminus \{2, 5\} = \{1, 3, 4\}\) is a vertex cover of size 3 in \(G\). Check: edge 1-2 covered by 1, edge 2-3 covered by 3, edge 3-4 covered by 3 and 4, edge 4-5 covered by 4, edge 5-1 covered by 1, edge 1-3 covered by 1 and 3. All covered.
Polynomiality
Computing the complement graph: check all \(\binom{|V|}{2}\) pairs, flip edges. Time: \(O(|V|^2)\). Computing \(|V| - K\): \(O(1)\). Total: \(O(|V|^2)\) — polynomial.
Conclusion. CLIQUE ∈ NP (polynomial verifier) + CLIQUE is NP-Hard (VC \(\leq_p\) CLIQUE, chained with 3-SAT \(\leq_p\) VC) = CLIQUE is NP-Complete.
Intermezzo: NP-Hardness in the Wild
NP-completeness reductions aren't just abstract theory — they've been used to prove that classic video games are computationally hard.
Theorem (Aloupis et al., 2012). "It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros."
The proof uses a reduction from 3-SAT. The paper constructs "gadgets" in Mario levels — specific arrangements of blocks, enemies, and platforms — that simulate Boolean variables (choose left or right path = TRUE or FALSE) and clauses (a section passable only if at least one literal is true). The same technique proves NP-hardness for Legend of Zelda, Metroid, and Pokemon.
This "gadget" approach is a general technique: build physical or logical components from the target domain that simulate Boolean logic. If your game/problem can encode arbitrary 3-SAT instances, it's NP-hard.
HAMC \(\leq_p\) HAMP
The final reduction connects two closely related problems: Hamiltonian Cycle and Hamiltonian Path.
Problem Definitions
HAMILTONIAN CYCLE (HAMC).
Instance: A graph \(G = (V, E)\).
Question: Is there a simple cycle that visits all vertices exactly once?
HAMILTONIAN PATH (HAMP).
Instance: A graph \(G = (V, E)\).
Question: Is there a simple path that visits all vertices exactly once?
Key difference: HAMC requires returning to the start (a cycle); HAMP just needs a path through every vertex. HAMC is NPC by a known (complex) reduction from 3-SAT — stated here without proof ("proof by intimidation"). We use HAMC as our starting point to prove HAMP is NPC.
Step 1: HAMP is in NP
HAMP ∈ NP — Polynomial-time verifier
Certificate: A sequence of vertices \((v_1, v_2, \ldots, v_{|V|})\) — the proposed path.
Verifier:
- Check that every vertex appears exactly once in the sequence.
- Check that consecutive pairs \((v_i, v_{i+1})\) are connected by edges in \(G\).
Running time: \(O(|V|^2)\) — polynomial. Certificate size: \(|V|\) — polynomial.
Step 2: The Reduction — Add Three Nodes
Given a HAMC instance \(I = (V, E)\), construct a HAMP instance \(f(I) = (V', E')\):
Construction.
- Pick an arbitrary vertex \(v_1 \in V\).
- Add three new nodes: \(V' = V \cup \{a, b, c\}\).
- Add edges:
- \(\{b, v_1\}\) — connect \(b\) to \(v_1\)
- \(\{a, c\}\) — connect \(a\) to \(c\)
- \(\{c, u\}\) for every \(u\) such that \(\{v_1, u\} \in E\) — connect \(c\) to all neighbours of \(v_1\)
- \(E' = E \cup \{\{b, v_1\}, \{a, c\}\} \cup \{\{c, u\} \mid \{v_1, u\} \in E\}\)
The intuition: Node \(c\) is a "clone" of \(v_1\)'s connectivity. Nodes \(a\) and \(b\) are degree-1 endpoints that force any Hamiltonian path to start at one and end at the other. The construction "breaks open" the cycle at \(v_1\):
A Hamiltonian cycle \(v_1 \to \cdots \to v_{\text{last}} \to v_1\) becomes the path \(b \to v_1 \to \cdots \to v_{\text{last}} \to c \to a\). The cycle's closing edge \(\{v_{\text{last}}, v_1\}\) is replaced by going through \(c\) (which inherits \(v_1\)'s connections) and then to \(a\).
Worked Example
Applying the reduction
HAMC instance: \(V = \{v_1, v_2, v_3, v_4, v_5\}\) with Hamiltonian cycle \((v_1, v_2, v_3, v_4, v_5, v_1)\).
Pick \(v_1\). Its neighbours: \(v_2\) and \(v_5\) (from the cycle edges).
New graph: \(V' = \{v_1, v_2, v_3, v_4, v_5, a, b, c\}\).
New edges: \(\{b, v_1\}\), \(\{a, c\}\), \(\{c, v_2\}\), \(\{c, v_5\}\).
The Hamiltonian path: \((b, v_1, v_2, v_3, v_4, v_5, c, a)\) — visits all 8 vertices, uses only valid edges.
Soundness: Both Directions
Forward: \(I \in \text{HAMC} \implies f(I) \in \text{HAMP}\)
Let \(\gamma = (v_1, v', \ldots, v'', v_1)\) be a Hamiltonian cycle in \((V, E)\).
- \(\pi = (v_1, v', \ldots, v'')\) is a Hamiltonian path through all of \(V\). (Just remove the final edge back to \(v_1\).)
- Since \(\{b, v_1\} \in E'\), prepend \(b\): we get \((b, v_1, v', \ldots, v'')\).
- Since \(\{v'', v_1\} \in E\) (the closing edge of \(\gamma\)), and \(c\) is connected to all of \(v_1\)'s neighbours, we have \(\{v'', c\} \in E'\).
- Since \(\{c, a\} \in E'\), append \(c, a\).
- Result: \(\pi' = (b, v_1, v', \ldots, v'', c, a)\) is a Hamiltonian path in \(G'\) visiting all \(|V| + 3\) vertices. \(\square\)
Backward: \(f(I) \in \text{HAMP} \implies I \in \text{HAMC}\)
Let \(\pi'\) be a Hamiltonian path in \((V', E')\).
- Key observation: Nodes \(a\) and \(b\) each have degree 1 in \(G'\). Node \(a\) connects only to \(c\). Node \(b\) connects only to \(v_1\). An internal node on a path needs degree \(\geq 2\), so \(a\) and \(b\) must be the endpoints of \(\pi'\).
- The path has form: \(\pi' = (b, v_1, \ldots, v_{\text{last}}, c, a)\) or the reverse.
- Node \(v_{\text{last}}\) is adjacent to \(c\) in \(E'\). By construction, \(c\)'s neighbours are exactly \(v_1\)'s neighbours in \(E\). So \(\{v_{\text{last}}, v_1\} \in E\).
- The subpath \((v_1, \ldots, v_{\text{last}})\) visits all vertices of \(V\). Adding the edge \(\{v_{\text{last}}, v_1\}\) closes it into a Hamiltonian cycle in \((V, E)\). \(\square\)
Polynomiality
| Step |
Operation |
Time |
| 1 |
Add three new nodes |
\(O(|V|)\) |
| 2 |
Add edges for \(b\), \(a\)-\(c\), and \(c\)'s neighbourhood |
\(O(|E|)\) |
Total: \(O(|V| + |E|)\) — linear. As polynomial as it gets.
Conclusion. HAMP ∈ NP (polynomial verifier) + HAMP is NP-Hard (HAMC \(\leq_p\) HAMP) = HAMP is NP-Complete.
Why All Three Nodes Are Needed
Could we simplify by using just \(b\) and \(c\) (skipping \(a\))? No.
Without \(a\), node \(c\) would have degree \(\geq 2\) (connected to all of \(v_1\)'s neighbours). That means \(c\) is no longer forced to be an endpoint — a Hamiltonian path could enter \(c\) from one neighbour and exit to another, bypassing the structural guarantee. The path might use \(c\) as an internal node, breaking the correspondence between paths in \(G'\) and cycles in \(G\).
Node \(a\) (degree 1, connected only to \(c\)) forces \(c\) to be the second-to-last node, which forces the path to end at \(a\). Together with \(b\) (degree 1, connected only to \(v_1\)), this pins both endpoints, ensuring every Hamiltonian path has the form \((b, v_1, \ldots, c, a)\) — which is exactly the "opened" cycle.
The general principle. In reduction constructions, degree-1 nodes (pendant vertices) are a common technique to force specific structure. By limiting a node's connectivity, you constrain where it can appear in any solution. Whenever you see "add a new node connected only to X," it's forcing X to be adjacent to an endpoint.
Broken Reductions
One of the most important exam skills: given a proposed reduction, can you spot what's wrong with it? Broken reductions all share a common flaw, and once you see the pattern, it's easy to catch.
The Broken Example
A proposed reduction from HAMP to some problem X
- Add three new nodes to \(V\). (\(V' = V \cup \{a, b, c\}\))
- Connect \(b\) to the first node in the path \(\pi\).
- Do more stuff.
What's wrong: Step 2 says "the first node in the path \(\pi\)." But \(\pi\) is the Hamiltonian path — the thing we're trying to determine the existence of!
The fundamental rule: a reduction cannot reference the solution.
A reduction maps
instances to
instances. It takes a graph (the question) and outputs a transformed graph (a different question). It must work for
both yes-instances (where a solution exists) and no-instances (where no solution exists). If the reduction says "take the solution and..." then:
- It only works when the answer is "yes" (the solution exists).
- For "no" instances, there IS no solution to reference — the reduction is undefined.
- Even if you could find the solution, that would take exponential time (the problem is NPC), so the reduction wouldn't be polynomial.
Compare to the correct HAMC \(\leq_p\) HAMP reduction: Step 1 says "pick an arbitrary node \(v_1\)." Not "pick the first node in the cycle." The choice of \(v_1\) is made without knowing whether a cycle exists. This is the critical difference.
Another Broken Pattern: Circular Reductions
Consider this "reduction" from 3-SAT to PATH:
A circular "reduction" (broken!)
- On input \(\langle U, C \rangle\): solve \(\langle U, C \rangle\) in polynomial time (assuming P = NP).
- If satisfiable: output a yes-instance of PATH (e.g., two connected nodes \(s, t\)).
- If unsatisfiable: output a no-instance of PATH (e.g., two disconnected nodes \(s, t\)).
What's wrong: This assumes P = NP in step 1 — the very thing that NPC reductions help us understand! A valid reduction must work unconditionally, without assuming the answer to the P vs NP question. This "reduction" is circular and tells us nothing about the relative difficulty of the problems.
How to Spot Broken Reductions (Checklist)
A valid polynomial-time reduction must:
- Work on instances, not solutions. It takes the problem description as input. Never "given a solution..." or "take the first element of the path..."
- Work for both yes- and no-instances. If the reduction only makes sense when the answer is "yes," it's broken.
- Run in polynomial time. No "solve the NPC problem first" steps.
- Be unconditional. No "assuming P = NP" or other unproven hypotheses.
- Preserve the answer in both directions. Yes maps to yes AND no maps to no. If you can only prove one direction, the reduction is incomplete.
Exam Skills: Applying & Critiquing Reductions
The exam won't ask you to invent reductions. Instead, you'll need three skills:
Skill 1: Apply a Reduction to a Specific Instance
Given a 3-SAT formula, produce the VC graph. Given a VC instance, produce the CLIQUE instance. Given a graph, apply the HAMC-to-HAMP construction. Practice this mechanically — follow the steps, draw the graph, compute K.
Practice template: 3-SAT to VC
- List all variables. Draw one edge \(\{u, \neg u\}\) per variable. (Proposition edges.)
- List all clauses. Draw one triangle per clause. Label triangle nodes with the clause's literals. (Clause triangles.)
- For each triangle node, draw an edge to the matching literal node. (Connection edges.)
- Compute \(K = |U| + 2|C|\). Count nodes and edges as a sanity check: \(2|U| + 3|C|\) nodes, \(|U| + 3|C| + 3|C|\) edges.
- Pick a satisfying assignment. Verify the cover has exactly \(K\) nodes and covers all edges.
Skill 2: Critique a Proof of Correctness
Given a reduction and a claimed proof, check:
- Forward direction: Does a yes-instance of the source really produce a yes-instance of the target? Trace through the proof — does each step follow?
- Backward direction: Does a yes-instance of the target really imply the source was a yes-instance? This is where most errors hide.
- Tightness: Does the proof account for the exact budget (K)? Are there hidden assumptions about what the cover/clique/path "must" look like?
- Solution-dependence: Does any step reference the solution rather than the instance?
Skill 3: Fix a Broken Reduction
When a reduction is broken (usually because it references the solution), the fix is typically: replace the solution-dependent step with an instance-level construction. For example, "connect to the first node in the path" becomes "connect to an arbitrary node."
Summary: The Complete Reduction Map
| Problem |
Definition |
NPC Proof |
| SAT |
Boolean satisfiability (CNF) |
Cook-Levin theorem (first NPC problem) |
| 3-SAT |
SAT with exactly 3 literals per clause |
SAT \(\leq_p\) 3-SAT (split long clauses) |
| Vertex Cover |
\(\exists V' \subseteq V\), \(|V'| \leq K\), covers all edges |
3-SAT \(\leq_p\) VC (proposition edges + clause triangles + connections, \(K = |U| + 2|C|\)) |
| Clique |
\(\exists V' \subseteq V\), \(|V'| \geq K\), all pairs connected |
VC \(\leq_p\) CLIQUE (complement edges, \(K' = |V| - K\)) |
| HAMC |
Simple cycle visiting all vertices |
NPC by standard result (not proven in this course) |
| HAMP |
Simple path visiting all vertices |
HAMC \(\leq_p\) HAMP (add 3 nodes \(a, b, c\)) |
The NPC proof pattern (for every problem above).
- NP membership: Give a polynomial-size certificate and a polynomial-time verifier.
- NP-hardness: Reduce FROM a known NPC problem TO the target. Show the reduction is polynomial, and prove soundness in both directions (yes → yes AND yes ← yes).
The story arc. This page completes the complexity theory arc of the course. We went from "what can be computed?" (decidability) to "what can be computed efficiently?" (P vs NP) to "which problems are the hardest in NP?" (NPC). The reductions on this page are the concrete evidence: SAT, Vertex Cover, Clique, and Hamiltonian Path are all equally hard — solve any one in polynomial time and you've solved them all.
The big open question remains: is there a polynomial-time algorithm for any of them? Nobody knows. But if you ever find one, you've earned a million dollars and broken modern cryptography.