Does k-PATH admit a constant approximation?
Karger, Motwani and Ramkumar (1997) discuss this question.
They show that if any polynomial-time algorithm can approximate the longest path to a ratio of $2^{O(\log^{1−\epsilon} n)}$, for any $\epsilon&gt;0$, then NP has a quasi-polynomial deterministic time simulation; this results even holds for graphs of bounded degree.


  David R. Karger, Rajeev Motwani, G. D. S. Ramkumar:
  On Approximating the Longest Path in a Graph.
  Algorithmica 18(1): 82-98 (1997)