2
$\begingroup$

The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.

For example if for $k=1$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $O(n\log n)$.

My question is what happens when $k$ increases - does the solution become more and more complex or is it the same for all values of $k$ larger than $1$?

$\endgroup$
2
$\begingroup$

Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity.

Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms:

  1. For every fixed $k$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
  2. Trevisan showed that there is no PTAS when $k = \log n$ (unless P=NP).
  3. Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $k$!
$\endgroup$
  • $\begingroup$ Can you clarify what you mean by "The same isn't known for fixed k"? Does this mean that it may or may not be NP-hard? $\endgroup$ – Vikas Shetty May 16 at 8:12
  • $\begingroup$ That’s right. We simply don’t know. $\endgroup$ – Yuval Filmus May 16 at 8:36

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.