patternMinor
Is there an efficient solution to the travelling salesman problem with binary edge weights?
Viewed 0 times
salesmanproblemthesolutionwithweightsefficientedgetravellingbinary
Problem
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
Solution
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.)
Context
StackExchange Computer Science Q#105984, answer score: 8
Revisions (0)
No revisions yet.