).
| TSP | metric TSP | |
|---|---|---|
| ratio of 1 | NP-hard | NP-hard |
| ratio of 2 | NP-hard | polynomial |
Proved the hardness results for exact metric TSP already (since ).
The hardness for a ratio of 2 come from replacing the distance 2 edges with distance 2 n edges (violating the ``metric'' property). Then, if there is a Hamiltonian circuit, the approximation algorithm would have to give us a tour of length no more than 2 n. Such a tour could only consist of the length 1 edges and, therefore, would indicate the existence of a Hamiltonian circuit in the original graph.
