# 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>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>0$, then NP has a quasi-polynomial deterministic time simulation; this results even holds for graphs of bounded degree.