3SAT → HAMPATH · gadget reduction

3SAT ≤_p HAMPATH (Sipser §7.5). The reduction builds a graph whose Hamiltonian paths correspond to satisfying assignments. Two pieces:

The Hamiltonian path must visit each c_j. The only way to do so without breaking the diamond's required traversal is to use an edge that the assigned literal makes "available" — i.e., an edge in a diamond being traversed in the direction matching the clause's literal. So a Hamiltonian path exists iff every clause has at least one true literal.

• The diamond is more than a chain. It has internal structure that forces directional traversal — you can't half-traverse. Sipser's Figure 7.49 shows the precise wiring.
• Each clause node must be visited exactly once. Hamiltonian = every vertex used once. The spreaders are visited via "side trips" from the diamonds.
• Gadget reductions look ad hoc but aren't. Every move in the diamond/spreader design serves a precise logical role. Don't be intimidated by the complexity — each piece encodes one logical constraint.

• Q1. What does "traversal direction = assignment" mean?
  Each variable diamond has two valid Hamiltonian traversals: left-to-right (encoding x_i = true) or right-to-left (encoding x_i = false). The Hamiltonian path picks one direction per diamond, and the collection of choices defines a Boolean assignment.
• Q2. How does the clause spreader work?
  For each clause C, the clause node c_j connects to specific edges inside the diamonds. Crucially: an edge inside x_i's diamond is "available for c_j's visit" only when that diamond is being traversed in the direction matching the literal in C. So visiting c_j requires that at least one of its literals is true.
• Q3. Size of the gadget?
  The diamond for each variable has O(m) nodes (to accommodate connections to all clauses), so the whole graph has O(n·m) nodes and O(n·m) edges. Polynomial in formula size.

Sipser: Theorem 7.46, Figures 7.49–7.51. Lecture notes: Module 5 slide 5. Companion problems: P23 (HAMPATH verifier), P29 (SUBSET-SUM).