# Is there an efficient solution to the travelling salesman problem with binary edge weights?

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

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.)

• 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. Mar 24, 2019 at 11:16
• @JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles? Mar 24, 2019 at 14:43
• 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? Mar 24, 2019 at 15:00
• @WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.) Mar 24, 2019 at 19:39
• @immibis: That (and the question of whether the underlying graph is complete or not) would depend on how the question is formulated, and I don't know if there is a definitively canonical definition of TSP. FWIW, the definition on p. 211 of Garey & Johnson (1979) specifies the output as a permutation of the vertices, implying the(ir) answer is "no". (They also require distances to be in $\mathbb Z^+$ for each pair of cities, which actually rules out 0-length edges, making the 0-1 TSP problem described here technically not a special case of TSP...) Mar 25, 2019 at 11:19

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.

• 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! Mar 25, 2019 at 11:24
• @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.) Mar 25, 2019 at 11:29