<p><s>I'm pretty sure that the best known polynomial time solution is still Alon, Yuster, and Zwick's color coding technique (<a href="http://doi.acm.org/10.1145/210332.210337" rel="nofollow">JACM 1995</a>) which finds paths of logarithmic length in polynomial time (without needing the assumptions that the graph is cubic and Hamiltonian, only that it has a path of that length).</s> This part is not the best known; see Björklund's answer for longer paths in polynomial time.</p>

<p>A related problem is the best (exponential) time bound for finding the whole Hamiltonian cycle, which I believe is O(1.251^n) due to Iwama and Nakashima (<a href="http://dx.doi.org/10.1007/978-3-540-73545-8_13" rel="nofollow">COCOON 2007</a>) improving <a href="http://arxiv.org/abs/cs.DS/0302030" rel="nofollow">one of my papers</a>.</p>

CC BY-SA 2.5
2010-08-27T20:31:35.753Z
Hi David, What is the current lower bound?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T23:32:39.717Z
@turkistany: we don't have good lower bounds for any NP-hard problems!
Emil
CC BY-SA 2.5
2010-08-28T00:23:18.547Z
@Emil, I mean inapproximability lower bound.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-28T06:55:11.757Z
Björklund and his ICALP'04 coauthors wrote "this problem is notorious for the difficulty of understanding its approximation hardness." They did succeed in showing that the directed version of longest path is hard to approximate to within better than a n^{1-ε} factor, though.
David Eppstein
CC BY-SA 2.5
2010-08-28T06:59:49.220Z
Also, Karger, Motwani, and Ramkumar, Algorithmica 1997, show that the undirected longest path problem is hard to approximate within a constant and that, for all ε < 1, it's hard to find paths in Hamiltonian graphs that are longer than n – n^ε.
David Eppstein
CC BY-SA 2.5
2010-08-27T19:16:56.353Z
2010-08-27T20:23:07.123Z
2010-08-27T20:23:07.123Z
David Eppstein
<p>Check out
"Finding long paths and cycles in sparse Hamiltonian graphs"
by Feder, Motwani, and Subi from STOC 2000. AFAIK, this is the best algorithm known to date.</p>

CC BY-SA 2.5
2010-08-27T19:19:14.527Z
2010-08-27T19:19:14.527Z
Andreas Björklund
<p>Well, it is trivial. There is a path on $n$ vertices, as the graph is Hamiltonian. Perhaps you meant to ask something else?</p>

CC BY-SA 2.5
2010-08-27T13:48:30.253Z
This is not a decision problem, we want an polynomial-time algorithm that produces longest path possible
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T13:50:32.187Z
Well, you said "approximating", so the only reasonable interpretation is that you wanted (an approximation to) the *length* of the longest path. Could you edit your question?
Emil
CC BY-SA 2.5
2010-08-27T14:04:58.443Z
The standard interpretation in the field of approximation algorithms is to provide an algorithm that produces the longest path in the given graph.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-27T15:44:22.857Z
That makes no sense. We know there's a path of length n, so unless you have reason to believe that even the promise problem is hard, what's the approximation issue ?
Suresh Venkat
CC BY-SA 2.5
2010-08-27T13:42:12.527Z
2010-08-27T13:42:12.527Z
Emil
<p><strong>optimization problem</strong></p>

<p><strong>Input</strong>: cubic Hamiltonian graph</p>

<p><strong>feasible solution</strong>: A simple path</p>

<p><strong>measure to optimize</strong>: length of the simple path</p>

<p>Design a polynomial-time algorithm that outputs the longest path it can find. </p>

<p>To my knowledge, longest path problem does not have polynomial-time constant-factor approximation in cubic Hamiltonian graphs unless P=NP. This problem is interesting since the input is cubic graph and has a n-length Hamiltonian cycle.</p>

<p><a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WH3-45JCBNT-H&amp;_user=3672885&amp;_coverDate=04%2F30%2F1999&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1443483023&amp;_rerunOrigin=google&amp;_acct=C000058889&amp;_version=1&amp;_urlVersion=0&amp;_userid=3672885&amp;md5=1d609c736300cebbec02aa8aa17b99c5" rel="nofollow">On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs</a>, Journal of Algorithms 31, 249-268, 1999.</p>

CC BY-SA 2.5
2010-08-27T15:09:32.033Z
You should provide some more detail and background for your questions. As Emil answers below, the questions sounds entirely trivial since there is always a path of length n on a Hamiltonian graph. Can you edit the question to make it clearer?
Robin Kothari
CC BY-SA 2.5
2010-08-27T16:09:36.333Z
edited text to make it clearer.
Suresh Venkat
CC BY-SA 2.5
2010-08-27T17:46:46.010Z
@Suresh: the question is more sensible now. But what does  "constant-factor approximation" mean in this context?
Emil
CC BY-SA 2.5
2010-08-27T18:06:31.997Z
well since the longest path is of size $n$, it seems that finding any path of length cn, for any constant n, appears to be hard. Maybe the OP wants to know if one can find a path of length n/log n, for example.
Suresh Venkat
<ds.algorithms><reference-request><graph-theory><hamiltonian-paths>
Best bounds for the longest path optimization problem in cubic Hamiltonian graph?
Mohammad Al-Turkistany
# Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

(Asked by: username_0 on 2010-08-27)

**optimization problem**

**Input**: cubic Hamiltonian graph

**feasible solution**: A simple path

**measure to optimize**: length of the simple path

Design a polynomial-time algorithm that outputs the longest path it can find.

To my knowledge, longest path problem does not have polynomial-time constant-factor approximation in cubic Hamiltonian graphs unless P=NP. This problem is interesting since the input is cubic graph and has a n-length Hamiltonian cycle.

[On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45JCBNT-H&_user=3672885&_coverDate=04%2F30%2F1999&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1443483023&_rerunOrigin=google&_acct=C000058889&_version=1&_urlVersion=0&_userid=3672885&md5=1d609c736300cebbec02aa8aa17b99c5), Journal of Algorithms 31, 249-268, 1999.

**Tags:** ds.algorithms, reference-request, graph-theory, hamiltonian-paths
> **Comments:**
> **username_1**: You should provide some more detail and background for your questions. As Emil answers below, the questions sounds entirely trivial since there is always a path of length n on a Hamiltonian graph. Can you edit the question to make it clearer?  
> **username_2**: edited text to make it clearer.  
> **username_3**: @Suresh: the question is more sensible now. But what does  "constant-factor approximation" mean in this context?  
> **username_2**: well since the longest path is of size $n$, it seems that finding any path of length cn, for any constant n, appears to be hard. Maybe the OP wants to know if one can find a path of length n/log n, for example.  

---

## 3 answers

### Answer by username_4 on 2010-08-27. Score: 4 | Accepted answer

~~I'm pretty sure that the best known polynomial time solution is still Alon, Yuster, and Zwick's color coding technique ([JACM 1995](http://doi.acm.org/10.1145/210332.210337)) which finds paths of logarithmic length in polynomial time (without needing the assumptions that the graph is cubic and Hamiltonian, only that it has a path of that length).~~ This part is not the best known; see Björklund's answer for longer paths in polynomial time.

A related problem is the best (exponential) time bound for finding the whole Hamiltonian cycle, which I believe is O(1.251^n) due to Iwama and Nakashima ([COCOON 2007](http://dx.doi.org/10.1007/978-3-540-73545-8_13)) improving [one of my papers](http://arxiv.org/abs/cs.DS/0302030).

> **Comments:**
> **username_0**: Hi David, What is the current lower bound?  
> **username_3**: @turkistany: we don't have good lower bounds for any NP-hard problems!  
> **username_0**: @Emil, I mean inapproximability lower bound.  
> **username_4**: Björklund and his ICALP'04 coauthors wrote "this problem is notorious for the difficulty of understanding its approximation hardness." They did succeed in showing that the directed version of longest path is hard to approximate to within better than a n^{1-ε} factor, though.  
> **username_4**: Also, Karger, Motwani, and Ramkumar, Algorithmica 1997, show that the undirected longest path problem is hard to approximate within a constant and that, for all ε < 1, it's hard to find paths in Hamiltonian graphs that are longer than n – n^ε.  

---

### Answer by username_5 on 2010-08-27. Score: 8

Check out
"Finding long paths and cycles in sparse Hamiltonian graphs"
by Feder, Motwani, and Subi from STOC 2000. AFAIK, this is the best algorithm known to date.


---

### Answer by username_3 on 2010-08-27. Score: 2

Well, it is trivial. There is a path on $n$ vertices, as the graph is Hamiltonian. Perhaps you meant to ask something else?

> **Comments:**
> **username_0**: This is not a decision problem, we want an polynomial-time algorithm that produces longest path possible  
> **username_3**: Well, you said "approximating", so the only reasonable interpretation is that you wanted (an approximation to) the *length* of the longest path. Could you edit your question?  
> **username_0**: The standard interpretation in the field of approximation algorithms is to provide an algorithm that produces the longest path in the given graph.  
> **username_2**: That makes no sense. We know there's a path of length n, so unless you have reason to believe that even the promise problem is hard, what's the approximation issue ?  

---

