Shortest Hamilton Path Planar Problem

Question

I think that the problem to obtain the shortest path visiting once time each point (it is not needed to come back to start point so it is a Hamilton path), in its planar euclidean and symmetric version is an NP-complete problem.

Wikipedia says:

"If the distance measure is a metric and symmetric, the problem becomes APX-complete"

I´m not sure if wikipedia is correct, please can anyone clarify if this problem is NP-complete, APX-complete or both? Thanks in advance.

Answer 1

This problem is polynomially equivalent to the (minimum) Traveling Salesman Problem (TSP). It cannot be NP-complete since it is not a decision problem, but it is surely NP-hard, because the Hamiltonian Cycle Problem is a particular case of TSP and is NP-complete.

$\Delta$TSP problem is TSP with metrics (triangle inequality). It is known to be APX-hard (the referred article is here, however authors don't operate terms of APX, since this class was introduced later). More precisely it is polynomially $\frac32$-approximable, but is NP-hard to be $(1+\varepsilon)$-approximated for small enough positive $\varepsilon$. Also $\Delta$TSP belongs to APX, so it is APX-complete.

So your problem is NP-hard and APX-complete, too. (By the way the first statement follows from the last one.)

Answer 2

Cristos H. Papadimitriou says that "The Euclidean Travelling Salesman Problem Is NP-Complete" He based its demonstration reducing the Exact Cover Problem to it, wich is known NP-complete. In general the ETSP is NP-hard when the inputs are real coordenates, but restricting the input to integers such as the distances can be P computables, it is NP-complete. This is explained in page 239: "In what follows we will assume that the elements of the distance matrix are the integral parts of this metric. Any desired precision can be thus obtained by increasing the scale accordingly. Moreover in the constructions that will follow we will also allow rational coordinates, with the understanding that the scale will be eventually multiplied by an adequately large integer, so that all coordinates become integral and any necessary precision is obtained."

Ola Svensson in "Approximation Algorithms and Hardness of Approximation" is using a similar restriction to the inputs to obtain a PTAS with the Sanjeev Arora´s method wich has a $(1 + 1/c)-approximation$ where $c$ is the number of dimensions of the coordinates inputs; 3/2-aproximation for the planar problem is not good enough aproach.

So, the Shortest Hamilton Path Planar Problem, even restrincting inputs to a P computable distances is NP-complete, and APX-complete too.