3. Unapproximable Instances of TSP

Triangle Inequality

The Triangle Inequality is satisfied when $d(x,y)+d(y,z)\ge d(x,z)$.

Link to original

TSP is unapproximable whenever $d$ does not satisfy the Triangle Inequality.

The Travelling Salesman Problem is unapproximable whenever $d$ does not satisfy the triangle inequality.

1. Assume (for contradiction) that there is some polynomial time approximate algorithm for TSP whose approximation ratio is $R$.

2. $\text{length of}(H_{\text{approx}})\ge R\cdot \text{length of}(H_{\text{global}})$

3. Consider an instance of the Hamiltonian Cycle problem $G=(V,E)$. We use this to construct an instance of TSP that has a “short” approximate solution iff $G$ has a Hamiltonian cycle.

4. Construct a complete weighted graph $G^{\prime }=(V,d)$ by setting:

   $$d(x,y)=\{\begin{array}{ll}1& \text{if }(x,y)\in E\\ nR+1& \text{if }(x,y)\notin E\end{array}$$

   

5. Let $H_{\text{approx}}$ be the cycle returned by the approximate algorithm. Then $\text{length of}(H_{\text{approx}})\le nR⟺G\text{ has a Hamiltonian cycle}$. Considering this from left-to-right:

   • Suppose $H_{\text{approx}}$ is a ‘short’ TSP cycle.
   • $\text{length of}(H_{\text{approx}})\le nR$
   • $H_{\text{approx}}$ must only use ‘short edges’ of length $q$
   • Therefore, $H_{\text{approx}}$ must be a Hamiltonian cycle of $G$

   Considering this from right-to-left:

   • Suppose that $G$ has a Hamiltonian cycle.
   • Then there is a TSP path $H_{\text{global}}$ that only uses ‘short’ edges.
   • $\text{length of}(H_{\text{global}})=\underset{n\text{ vertices}}{\underbrace{1+1+\dots +1}}=n$
   • But we assumed that $\text{length of}(H_{\text{approx}})\le R\cdot \text{length of}(H_{\text{global}})$
   • Hence, $\text{length of}(H_{\text{approx}})\le R\cdot n$

6. Hence, we can use our hypothesized approximation algorithm to give an exact deterministic polynomial-time algorithm for the Hamiltonian cycle problem (see FAST-TSP).

7. Assuming that $P\ne NP$, we must conclude that the general case of the TSP is unapproximable as required.