0
$\begingroup$

It is known that the general traveling salesman problem is NP-hard. Even when the distances follow the triangle inequality. But let's take the problem very literally. There are actual cities (points) on a 2-d euclidean space and a tour must be devised to visit all of them in the smallest total distance. We are given the $x$ and $y$ coordinates of each city and the distances between them are the euclidean distances. Is this simplified problem also NP-hard?

$\endgroup$
1
  • $\begingroup$ The TSP is defined on graphs. I don't think that the planarity property makes the problem easier, just by obviousness: no textbook reports a "map" version as being tractable. Also, most graphs can have a planar embedding. $\endgroup$
    – user16034
    Jan 9, 2023 at 9:45

1 Answer 1

2
$\begingroup$

This is called the Geometric Traveling Salesman problem. It was proved to be NP-complete by Garey, Graham and Johnson in 1976 and Papadimitriou in 1977.

Source: Computers and Intractability (Garey and Johnson)

$\endgroup$
3
  • 1
    $\begingroup$ Does that include the case where the map is planar (no crossing lines)? If so, are there any non-NP-complete special cases? $\endgroup$ Jan 9, 2023 at 3:57
  • $\begingroup$ My guess is that it is still $\mathsf{NP}$-complete, yes. $\endgroup$
    – Nathaniel
    Jan 9, 2023 at 5:59
  • $\begingroup$ If you restrict it enough then it won’t be NP complete anymore. For example with the restriction “all distances must be the same “. $\endgroup$
    – gnasher729
    Jan 9, 2023 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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