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.

$\endgroup$
  • 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 '10 at 15:09
  • 2
    $\begingroup$ edited text to make it clearer. $\endgroup$ – Suresh Venkat Aug 27 '10 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 '10 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 '10 at 18:06
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.

$\endgroup$
  • $\begingroup$ Hi David, What is the current lower bound? $\endgroup$ – Mohammad Al-Turkistany Aug 27 '10 at 20:31
  • $\begingroup$ @turkistany: we don't have good lower bounds for any NP-hard problems! $\endgroup$ – Emil Aug 27 '10 at 23:32
  • $\begingroup$ @Emil, I mean inapproximability lower bound. $\endgroup$ – Mohammad Al-Turkistany Aug 28 '10 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 '10 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 '10 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.

$\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?

$\endgroup$
  • $\begingroup$ This is not a decision problem, we want an polynomial-time algorithm that produces longest path possible $\endgroup$ – Mohammad Al-Turkistany Aug 27 '10 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 '10 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 '10 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 '10 at 15:44

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.