Reducing TSP to Hamiltonian circuit

algorithm graph graph-algorithm np-complete reduction
Madu picture Madu · Nov 13, 2012 · Viewed 12k times · Source

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

Patricia Shanahan picture Patricia Shanahan · Nov 14, 2012

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

Related questions

Explanation of Algorithm for finding articulation points or cut vertices of a graph

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page. From reading around, I got to know the basic facts …

Read More
How to find if a graph is bipartite?

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union …

Read More
Algorithm for diameter of graph?

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity. Wikipedia says you can do this using …

Read More