HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.