# How to prove non-existence of $O(2^n)$ approximation algorithm solving TSP?

The following theorem (from "The Design of approximation algorithms" by Williamson & Shmoys, pg 43) states:

For any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm for the traveling salesman problem on $n$ cities, provided $P \neq NP$. In fact, the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$.

This theorem is given without a proof. It only explains, before the theorem formally stated, that for any $\alpha > 1$, there does not exist an $\alpha$-approximation algorithm. This part is clear. But the claim that the existence of an $O(2^n)$-approximation algorithm for the TSP would similarly imply that $P = NP$ is not obvious to me. Could someone give me a hint how to prove it or sketch of proof?

• Try using such an algorithm to determine if a given graph is Hamiltonian. – Yuval Filmus Nov 10 '17 at 23:19
• @YuvalFilmus Right. I missed that part of the discussion in the book. It says that we could set the weight of "non-edges" to $\alpha n + 2$ where $\alpha = O(2^n)$. So if the algorithm runs in $O(2^n)$ time, then it is, in fact, still polynomial of the length of input. Thanks! – HardFork Nov 11 '17 at 0:52
• Perhaps you should answer your own question now. – Yuval Filmus Nov 11 '17 at 6:22

## 1 Answer

After @YuvalFilmus' hint it turns out the answer lies in this book. The TSP can be used to solve the Hamiltonian Cycle problem by creating a new graph as following. Given $\alpha > 1$ and a graph $G=\langle V,E \rangle$ we create a new graph $G'=\langle V',E' \rangle$ such that $w(e')= 1$ if $e\in E$, and $w(e')= \alpha n+2$ if $e\notin E$. If $G$ has a Hamiltonian cycle then $G'$ has a tour of length $n$, otherwise each tour has length is at least $(\alpha+1)n + 1$.

Now we run $\alpha$-approximation algorithm for TSP and if the tour computed has cost at most $(\alpha+1)n$ then there is a Hamiltonian cycle in $G$, otherwise there doesn't. If we set $\alpha = O(2^n)$ then we have $O(2^n)$-approximation algorithm. This algorithm runs in $O(f(2^n))$ time for some polynomial $f$, but its time complexity is still polynomial in length of input. This means we would solve the Hamiltonian Cycle problem in polynomial time implying $P=NP$.

• You have to be a bit careful here, and check that this reduction is polytime. Indeed, you can't choose $\alpha$ arbitrarily large – it needs to be $2^{n^{O(1)}}$. – Yuval Filmus Nov 11 '17 at 8:39
• @YuvalFilmus wouldn't it be $2^{n^{O(f(n))}}$ where $f(n)$ is a polynomial? – HardFork Nov 11 '17 at 8:57
• It should be $2^{\mathit{poly}(n)}$, since we need the encoding to have polynomial length. – Yuval Filmus Nov 11 '17 at 8:58
• @YuvalFilmus Right, $n^{O(f(n))}$ is exponential. My mistake. – HardFork Nov 11 '17 at 9:06