2
$\begingroup$

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, Journal of Algorithms 31, 249-268, 1999.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – Robin Kothari
    Aug 27, 2010 at 15:09
  • 2
    $\begingroup$ edited text to make it clearer. $\endgroup$
    – Suresh Venkat
    Aug 27, 2010 at 16:09
  • $\begingroup$ @Suresh: the question is more sensible now. But what does "constant-factor approximation" mean in this context? $\endgroup$
    – Emil
    Aug 27, 2010 at 17:46
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Aug 27, 2010 at 18:06

3 Answers 3

Reset to default
4
$\begingroup$

I'm pretty sure that the best known polynomial time solution is still Alon, Yuster, and Zwick's color coding technique (JACM 1995) 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) improving one of my papers.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi David, What is the current lower bound? $\endgroup$
    – Mohammad Al-Turkistany
    Aug 27, 2010 at 20:31
  • $\begingroup$ @turkistany: we don't have good lower bounds for any NP-hard problems! $\endgroup$
    – Emil
    Aug 27, 2010 at 23:32
  • $\begingroup$ @Emil, I mean inapproximability lower bound. $\endgroup$
    – Mohammad Al-Turkistany
    Aug 28, 2010 at 0:23
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Aug 28, 2010 at 6:55
  • 1
    $\begingroup$ 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^ε. $\endgroup$
    – David Eppstein
    Aug 28, 2010 at 6:59
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is not a decision problem, we want an polynomial-time algorithm that produces longest path possible $\endgroup$
    – Mohammad Al-Turkistany
    Aug 27, 2010 at 13:48
  • $\begingroup$ 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? $\endgroup$
    – Emil
    Aug 27, 2010 at 13:50
  • $\begingroup$ The standard interpretation in the field of approximation algorithms is to provide an algorithm that produces the longest path in the given graph. $\endgroup$
    – Mohammad Al-Turkistany
    Aug 27, 2010 at 14:04
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Aug 27, 2010 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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