# Poly-Time TSP Algorithm if there is constant factor approximation algorithm?

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?

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