3
$\begingroup$

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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

By direct reduction, do you then mean a reduction that does not leave the graph-world and go back again? (that might be a very vague formulation, sorry). I do not think such a reduction exists. Of cause proving that it does not exist is not a simple matter, but at least I have not been able to find or think of one myself. But here's a couple of thoughts about why such a direct reduction is unlikely:

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.

You have most likely thought about this already, so this is mostly to say that you are not the only one who are not able to come up with such a reduction and I suspect that this may be because a reduction either has to be quite complicated or has to leave the graph-world somehow and go back again. Of cause there might exists a reduction that does leave the graph-world but is still simpler than going all the way through SAT, but I do not know of any such reduction.

I'm quite interested to see if anyone has a better answer to this.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    May 25, 2018 at 15:58
  • 1
    $\begingroup$ Yes, it is definitely a question of the definition of "direct reduction". A reduction through SAT exists, but SAT is not a graph problem and therefore I did not feel that it counted, but of cause my having to feel something to answer a question shows the lack of a proper definition. In this case though, OP asked for a reduction not involving SAT, and I took it to mean that they want a reduction not going through any other well-defined problems, hence my vague "not leaving the graph world." $\endgroup$
    – AstridNeu
    May 25, 2018 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.