Finding paths of length k

Tag: algorithm , graph , hadoop , mapreduce Author: yingelam Date: 2013-06-22

Given a graph with n nodes there are a number of serial methods of increasing sophistication and reducing complexity for finding simple paths of length k in a graph. The best known asymptotic complexity is currently O(2^k poly(n,k)) time. A naive algorithm on the other hand just enumerates all paths of length k and takes O(n^k) time (at least).

How could you translate the naive algorithm to work efficiently in the MapReduce paradigm? Are there existing libraries for this sort of thing?

Other Answer1

MapReduce is a parallelization framework, so the algorithm must be susceptible to parallelization to some extent, i.e. we can divide processing of solution space to independent sets. I guess that for the naive algorithm, you can tell each node to find k-1 long paths that begin with fixed graph node. For simplicity, if we have n machines, each of them can search k-1 paths that begin with 1, 2, ..., n. Of course parallelization gives only constant time improvement.