= Metric travelling salesman problem
= Metric TSP
{synonym}
This is the <travelling salesman problem> on a complete graph with nonnegative symmetric distances satisfying the <triangle inequality>. Repeated visits can be shortcut without increasing cost. Assigning distance one to edges of an input graph and two to its nonedges creates a metric instance with a tour of cost at most the number of vertices exactly when the graph has a <Hamiltonian cycle>. Thus the metric problem remains <NP-hard>.
Back to article page
