Reducing TSP to Hamiltonian circuit

Question

How can I convert the (decision version) of the traveling salesman problem to the Hamiltonian circuit problem (i.e. how to reduce TSP to HCP, so that if I have a solution to HCP, then I will use that solution to solve TSP problem)?

Answer 1

Every problem in NP can be polynomial-time reduced to any NP-complete problem - that is what makes the NP-complete problems so important.

Here's a chain of reductions:

1. Vertex Cover can be reduced to Hamiltonian Circuit.
2. 3-SAT can be reduced to Vertex Cover.
3. Satisfiability can be reduced to 3-SAT.
4. Any decision problem in NP can be reduced to Satisfiability (Cook-Levin theorem)

TSP is a problem in NP, so it can be reduced, in ridiculously long polynomial time, to Hamiltonian Circuit.

I got the reductions from Computers and Intractability: A Guide to the Theory of NP-Completeness