4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Try using such an algorithm to determine if a given graph is Hamiltonian. $\endgroup$ – Yuval Filmus Nov 10 '17 at 23:19
  • $\begingroup$ @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! $\endgroup$ – B.K. Nov 11 '17 at 0:52
  • $\begingroup$ Perhaps you should answer your own question now. $\endgroup$ – Yuval Filmus Nov 11 '17 at 6:22
4
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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)}}$. $\endgroup$ – Yuval Filmus Nov 11 '17 at 8:39
  • $\begingroup$ @YuvalFilmus wouldn't it be $2^{n^{O(f(n))}}$ where $f(n)$ is a polynomial? $\endgroup$ – B.K. Nov 11 '17 at 8:57
  • 2
    $\begingroup$ It should be $2^{\mathit{poly}(n)}$, since we need the encoding to have polynomial length. $\endgroup$ – Yuval Filmus Nov 11 '17 at 8:58
  • $\begingroup$ @YuvalFilmus Right, $n^{O(f(n))}$ is exponential. My mistake. $\endgroup$ – B.K. Nov 11 '17 at 9:06

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.