1
$\begingroup$

Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary?

Can someone provide a reference?

$\endgroup$
  • 1
    $\begingroup$ Weights are distances in Euclidean TSP, so I assume you mean that the coordinates are specified in unary. $\endgroup$ – Yuval Filmus Apr 12 '18 at 10:16
  • $\begingroup$ @YuvalFilmus Yes, indeed! (Though I hadn't thought of it this way before). Is it still NP-hard? $\endgroup$ – mathstudent42 Apr 12 '18 at 12:49
1
$\begingroup$

Yes, Papadimitriou in his "The Euclidean Traveling Salesman Problem Is NP-complete" paper reduces from Exact Cover to Euclidean TSP.

All the coordinates of the points are of polynomial magnitude.

And the required precision for the $L_0$ value in page 243 is to be able to distinguish between $a$ and ${(a^2+1)}^\frac12$. And near the end of page 241, he wrote "An adequate value of $a$ is 20." So the required precision is finite. Since you only have $n(4a + 13 + 2^\frac12)$, that would only magnify the difference.

All the page numbers above are in the proceedings containing his paper and can be seen once you have downloaded the paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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