Reduce Hamiltonian Cycle to TSP

Map an undirected graph to a complete weighted TSP instance and prove the threshold equivalence.

Problem

Given an undirected graph $G=(V,E)$ with $n\ge3$, construct a complete weighted graph on $V$ and threshold $B$ such that $G$ has a Hamiltonian cycle iff the resulting decision-TSP instance has a tour of cost at most $B$. Prove both directions, polynomial size, and NP membership.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Give original edges cost 1 and missing edges cost 2.

Hint 2

Every tour has exactly $n$ edges.

Hint 3

A tour itself is a polynomial certificate.

Full solution

Construct the complete graph $K_V$. Set $c(u,v)=1$ when $\{u,v\}\in E$ and $c(u,v)=2$ otherwise, and choose $B=n$. The construction lists $O(n^2)$ edges and uses one-bit costs, hence is polynomial.

If $G$ has a Hamiltonian cycle, use the same cyclic ordering in $K_V$. All its $n$ edges are original and have cost one, so the tour costs exactly $n$ and is feasible.

Conversely, every Hamiltonian tour in the complete graph contains exactly $n$ edges and each edge costs at least one. A tour of cost at most $n$ must therefore have cost exactly $n$, forcing every chosen edge to cost one. By construction all those edges belong to $E$, so the same cyclic ordering is a Hamiltonian cycle of $G$. This proves the many-one equivalence, including the equality boundary at the threshold.

Decision-TSP is in NP for integer costs encoded in binary: a certificate is a permutation of the vertices. The verifier checks that every vertex occurs once, adds the $n$ indicated edge costs using polynomial-bit arithmetic, includes the return edge, and compares the sum with $B$. Thus combining membership with the reduction from the NP-complete Hamiltonian-cycle problem proves NP-completeness of this TSP decision variant.

Completeness of the target graph matters. Missing source edges are not deleted; they receive a penalty. The threshold then ensures that a low-cost tour cannot use them. Using zero and one with threshold zero is also possible, but positive costs match common TSP definitions. This reduction proves decision hardness; it is not an approximation-preserving reduction and says nothing by itself about metric TSP, because costs 1 and 2 happen to satisfy the triangle inequality but the optimum gap is too small for arbitrary approximation claims.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Forgetting the closing edge of the tour.
• Using threshold $n$ without observing all costs are at least one.
• Claiming an approximation result from a decision reduction.

Sources and verification

• 2026 transcript 14
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT37 and ND22
• Corpus coverage note: No direct merged-summary coverage.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Hamiltonian Cycle → TSP