Recitation 8: NP-Complete Problems

What this lecture covers

This MIT 6.046 recitation practices the mechanics of NP-hardness reductions after the main lecture introduced P, NP, and NP-completeness. It answers a practical question: given a problem you already know is NP-hard, how do you construct a polynomial-time transformation that proves a new problem is NP-hard too, and how do you rigorously argue that the transformation preserves the yes/no answer in both directions?

The recitation works three examples of increasing difficulty. After watching, you should be able to reduce Hamiltonian cycle to Hamiltonian path, clique to independent set, and clique to Max-2-SAT, and you should understand why every such proof needs both an NP-membership argument and a two-directional correctness argument for the reduction.

Key ideas

• Reduction recipe: to prove problem B is NP-hard, take a known NP-hard problem A, give a polynomial-time transformation from any A-input to a B-input, and show the two instances have the same yes/no answer.
• Contrapositive logic: if B had a polynomial-time algorithm, composing the reduction with it would solve A in polynomial time; since A is assumed hard, B cannot be easy either.
• Certificates for NP membership: for each new problem, a short check-able solution (a path, an independent set, a variable assignment) shows the problem is in NP before showing it's hard.
• Vertex splitting: splitting a vertex into an "in" copy and an "out" copy converts a Hamiltonian cycle problem into a Hamiltonian path problem by breaking the cycle at one point.
• Complement graph: swapping edges and non-edges converts a clique in the original graph into an independent set in the complemented graph.
• Max-2-SAT: given clauses of at most two literals, decide whether some assignment satisfies at least K of them; reducing clique to it requires building clauses that reward exactly the vertices in a target clique.
• Two-directional correctness: a full reduction proof must show both that a solution to the source problem yields a solution to the target problem, and that a solution to the target problem can be converted back into a solution to the source problem.

Walkthrough

Recap and the reduction framework (0:00)

The recitation reviews P as problems with a polynomial-time decision algorithm and NP as problems whose answers are verifiable in polynomial time given a certificate. It then lays out the reduction template used for the rest of the session: to show problem B is NP-hard using known-hard problem A, build a polynomial-time function that transforms any input of A into an input of B with the same answer, so that an efficient algorithm for B would imply an efficient algorithm for A.

Hamiltonian cycle to Hamiltonian path (4:04)

Starting from the known-hard Hamiltonian cycle problem (a cycle visiting every vertex exactly once), the recitation reduces it to Hamiltonian path (a path, not necessarily closed, visiting every vertex). The transformation splits one chosen vertex into two copies, one keeping all incoming edges and one keeping all outgoing edges. The proof shows both directions: a Hamiltonian cycle through the original vertex becomes a Hamiltonian path once the vertex is split, and any Hamiltonian path in the split graph must start at the incoming-only copy and end at the outgoing-only copy, so merging them back recreates a cycle.

Clique to independent set (13:28)

The second reduction starts from the k-clique problem (does the graph contain a fully-connected subset of k vertices?) and targets independent set (does the graph contain a subset of k vertices with no edges between them?). The transformation simply complements the graph's edge set: every edge becomes a non-edge and vice versa. A clique in the original graph is then exactly an independent set in the complemented graph, since every pair connected before is disconnected after, and this argument is shown to hold in both directions.

Setting up clique to Max-2-SAT (21:47)

The final, more involved reduction targets Max-2-SAT: given 2-literal clauses, decide whether an assignment satisfies at least K of them. Given a graph and target clique size K, the construction creates one literal per vertex plus a dummy variable Z. It adds a clause (not x_i OR not x_j) for every non-edge (i,j), plus clauses (x_i OR Z) and (x_i OR not Z) for every vertex, and sets the satisfaction threshold to |complement edges| + |V| + K. The intuition is that setting exactly the clique's vertices to true (and everything else false) satisfies all the non-edge clauses, all the Z clauses, and exactly K of the not Z clauses.

Proving the Max-2-SAT reduction correct (28:53)

The recitation verifies the forward direction algebraically: assigning true to a size-K clique's vertices and false elsewhere satisfies every non-edge clause, every x_i OR Z clause, and exactly K of the x_i OR not Z clauses, matching the threshold. The reverse direction is harder: starting from an assignment that satisfies at least the threshold number of clauses, the recitation defines a candidate vertex set from the variables set to true, then shows that whenever this set contains a "violating" pair with no edge between them (so it isn't yet a clique), flipping that variable to false loses at most one satisfied clause but gains at least one back, leaving the total unchanged. Repeating this process removes all violations without lowering the satisfied-clause count, eventually producing an actual clique whose size, by the same counting argument, must be at least K.

Before you watch

• Review the definitions of P, NP, NP-hard, and NP-complete from the main lecture on complexity.
• Know the Hamiltonian cycle and clique problems as commonly cited NP-hard problems.
• Be comfortable reading Boolean clause notation such as (x_i OR not x_j).

Check your understanding

1. Why does a reduction from A to B need to run in polynomial time for the NP-hardness argument to work?
2. In the Hamiltonian path reduction, why must any Hamiltonian path in the split graph start at the incoming-only vertex copy?
3. Why does complementing a graph's edges turn a clique into an independent set?
4. In the Max-2-SAT reduction, why are the (x_i OR Z) and (x_i OR not Z) clauses needed in addition to the non-edge clauses?
5. In the reverse direction of the Max-2-SAT proof, why does flipping a violating vertex's variable to false never decrease the total number of satisfied clauses?