3
$\begingroup$

Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?

$\endgroup$
7
$\begingroup$

No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)

$\endgroup$
  • 3
    $\begingroup$ I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial. $\endgroup$ – John Dvorak Mar 24 at 11:16
  • $\begingroup$ @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles? $\endgroup$ – WiccanKarnak Mar 24 at 14:43
  • $\begingroup$ Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again? $\endgroup$ – John Dvorak Mar 24 at 15:00
  • $\begingroup$ @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.) $\endgroup$ – Eric Towers Mar 24 at 19:39
  • $\begingroup$ Aren't you allowed to use the same edge twice in TSP? $\endgroup$ – immibis Mar 24 at 22:00
2
$\begingroup$

The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.

However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is NP-complete.

$\endgroup$
  • $\begingroup$ This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $\mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP! $\endgroup$ – j_random_hacker Mar 25 at 11:24
  • $\begingroup$ @j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.) $\endgroup$ – David Richerby Mar 25 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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