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.

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

| cite | improve this answer | |
  • $\begingroup$ My impression (from the one seeming clarification I found during my skim of that paper) was that their results are about finding a fairly long path, rather than just approximating the length of the longest paths. ​ ​ $\endgroup$ – user6973 Mar 14 '16 at 14:45
  • 2
    $\begingroup$ @RickyDemer The hardness reduction should work for the length as well. $\endgroup$ – Chandra Chekuri Mar 14 '16 at 18:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.