# A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle with weight $\leq k$ which passes, once, through every vertex? (The weight of the cycle is the sum of the weights of the edges). The second problem is finding a Hamiltoninan Cycle (a cycle that passes through every vertex only once).

I know both are $NPC$. I am interested in finding reduction between both these problems. The first reduction $HamCycle \leq TSP$ is quite easy: for every edge in the original graph you give a weight $0$ and for every pair of vertices who did not have an edge you give a weight of $1$. Then you ask whether the agent can travel with sum of path $\leq 0$. The correctness of this follows pretty quickly.

However, my question if for the reduction the other way around: $TSP\leq HamCycle$. I could not come up with an idea for such. I am aware that since both are $NPC$ there exists a reduction through Cook-Levin Theorem and $SAT$, but I am wondering if there is a direct reduction $TSP\leq HamCycle$?

TSP is run on a fully connected graph with $n$ nodes and $n^2$ edges while HamCycle is run on a graph with $n$ nodes and $m < n^2$ edges (otherwise it would be trivial). A solution to TSP must pass all nodes and contain no cycles and therefore must contain exactly $n$ edges. We could run HamCycle each on all possible paths of length $n$, starting from the one with the lowest edge-sum and continuing until we reach one that contains a Hamiltonian Cycle, but as there are ${{n^2}\choose{n}} = O(n^{2n})$ such possible paths, this would mean running HamCycle an exponential number of times. I can not see how you can avoid this.
• Well, such a reduction must exist; simply compose the reductions for $TSP \le SAT$ and $SAT \le HamCycle$. When you compose them, this "never leaves the graph world". I think the problem is that the notion of "direct reduction" is not well-defined. – D.W. May 25 '18 at 15:58