Longest path approximation algorithm from a given node

views:

313

answers:

+5 Q:

Longest path approximation algorithm from a given node

Hi guys!

I'm looking for an approximation algorithm for the following problem - I have an unweighted, undirected graph, with cycles, and want to find the longest path starting from a given node. I do value speed over performance (so a O(n^5) algorithm would probably be an overkill).

This is not homework (I swear!) or work related, but I will appreciate any tip you might have.

+6 A:

I'm looking for an approximation algorithm for the following problem ...

Scientists are looking for it as well. They have also proved that polynomial constant-factor approximation doesn't exist if P ≠ NP. And the abstract of this article claims that it contains an approximation algorithm for your problem.

Pavel Shved 2010-02-08 10:29:25

Wow, I didn't know that. I thought the generalized problem has a constant factor approximation algorithm.What about restricting the problem even further, by having a maximum number of neighbors which is constant?

r0u1i 2010-02-08 11:09:25

@r0u1i, Whoops, the first article I linked also contains a proof that such restriction doesn't help :-).

Pavel Shved 2010-02-08 12:09:38

Thanks, You win :)

r0u1i 2010-02-08 12:29:07

Note though that NP-completeness result does not necessarily tell anything about the graph instances you work with. For example, SAT is NP-complete but huge SAT instances are solved routinely in industrial applications. Also, are your graphs planar? Can you restrict your (apparent) condition that you can visit a node only once? Does the process by which your graph is constructed give a hint to the nature of the longest paths?

antti.huima 2010-02-09 01:01:34

It is planar, what can I do with that?

r0u1i 2010-02-17 09:46:51

ansaurus

tags:

views:

answers:

Longest path approximation algorithm from a given node

related questions