<p>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.</p>

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

CC BY-SA 3.0
2016-03-14T18:25:11.233Z
@RickyDemer The hardness reduction should work for the length as well.
Chandra Chekuri
CC BY-SA 3.0
2016-03-14T14:18:39.750Z
2016-03-14T14:18:39.750Z
Gamow
<p>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$.</p>

<p>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$.</p>

<p><strong>Is there a constant $\alpha&gt;0$ for which $k$-PATH is $\alpha$-approximable in poly time?</strong></p>

CC BY-SA 3.0
2016-03-14T18:37:43.623Z
Gabow's paper on finding long paths of super poly-logarithmic length  is interesting and relevant. http://epubs.siam.org/doi/abs/10.1137/S0097539704445366
Chandra Chekuri
CC BY-SA 3.0
2016-03-14T18:38:39.723Z
There is also a paper on hardness for the longest path problem in directed graphs. http://link.springer.com/chapter/10.1007/978-3-540-27836-8_21#page-1
Chandra Chekuri
<cc.complexity-theory><ds.algorithms><approximation-algorithms>
Does k-PATH admit a constant approximation?
John D
# Does k-PATH admit a constant approximation?

(Asked by: username_0 on 2016-03-14)

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?**

**Tags:** cc.complexity-theory, ds.algorithms, approximation-algorithms
> **Comments:**
> **username_1**: Gabow's paper on finding long paths of super poly-logarithmic length  is interesting and relevant. http://epubs.siam.org/doi/abs/10.1137/S0097539704445366  
> **username_1**: There is also a paper on hardness for the longest path problem in directed graphs. http://link.springer.com/chapter/10.1007/978-3-540-27836-8_21#page-1  

---

## 1 answers

### Answer by username_2 on 2016-03-14. Score: 6

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)

> **Comments:**
> **username_1**: @RickyDemer The hardness reduction should work for the length as well.  

---

