CODEWITHSUNDEEP
algorithmgraph
Simd
Simd

Reputation: 21333

Finding long paths

I have a sparse unweighted directed graph of 1000000 nodes and I would like to find all simple paths of length 5. I know there will be very few simple paths of length 5 (maybe only one).

I see from http://en.wikipedia.org/wiki/Longest_path_problem that the parameterized complexity of determining if a graph has a path of length k is O(2^k n poly(n,k))) although I don't know if these methods will also solve my problem. Unfortunately all the methods I have found look very complicated and it seems unimplemented.

Can someone explain in more or less simple words a fast solution which I can then implement?

Upvotes: 1

Views: 155

Answers (1)

Falk Hüffner
Falk Hüffner

Reputation: 5040

I wrote an implementation of the Color-Coding method for Longest Path. However, it was only tested with graphs of about 10000 vertices; also, it might not find all size-5 paths (it was designed to find a small set of interesting paths). I might be able to adapt it to your purposes, drop me a line if you're interested.

Edit: The idea of Color-Coding is to randomly color the vertices of the graphs with 5 colors. The hope is that the 5 vertices of the path we're looking for all receive different colors. If this is true, we can find it with dynamic programming. Of course, the probability is only 0.0384; but if we repeat the whole procedure e.g. 500 times, there's only a chance of about 3*10^-9 that we miss it. That's just the basic scheme, there are many tricks to speed it up.

Upvotes: 2

Related Questions