I know that a polynomial-time constant factor approximation algorithm for the general Traveling Salesman Problem does not exist unless P=NP. However, I want to prove that the TSP decision problem (is there a Hamiltonian cycle of graph with weight sum <= k?) is in P if we assume that there is an approximation algorithm that guarantees optimal solution * a (a>1). Is there a way to prove this problem, without using polynomial reduction?

  • $\begingroup$ Hint: take $a$ close enough to 1. $\endgroup$ – Yuval Filmus Nov 28 '15 at 10:58
  • $\begingroup$ a is fixed constant in this problem. ex) 100 $\endgroup$ – YKS Nov 28 '15 at 12:02
  • $\begingroup$ What does the approximation algorithm return when there is no Hamiltonian cycle? $\endgroup$ – Yuval Filmus Nov 28 '15 at 12:17
  • $\begingroup$ Hamiltonian cycle always exists in TSP problem. Graph in the TSP is always complete graph with positive weights. $\endgroup$ – YKS Nov 28 '15 at 14:54
  • $\begingroup$ Are you familiar with the NP-completeness proof for TSP (the one that reduces from Hamiltonian cycle)? It might give you some ideas. $\endgroup$ – Tom van der Zanden Nov 29 '15 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.