Longest path approximation algorithm from a given node

Question

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.

Answer 1

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.