Does k-PATH admit a constant approximation? In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$.

A $\alpha$-approximation for $k$-PATH is an algorithm which given an input $\langle G,k\rangle$ either confirms that a path of length $k/\alpha$ exists in $G$, or denies the existence of a $k$-path. It may act arbitrarily if the longest simple path in $G$ is at least of size $k/\alpha$ and at most of size $k$.

Is there a constant $\alpha&gt;0$ for which $k$-PATH is $\alpha$-approximable in poly time?
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)