寻找长度为k的路径

Question

给定一个具有n个节点的图，有许多串行方法可以提高复杂度并降低复杂度，从而在图中找到长度为k的简单路径。目前最著名的渐近复杂度是O（2^k poly（n，k））时间。另一方面，一个天真的算法只枚举长度为k的所有路径，并花费O（n^k）时间（至少）。

如何将天真的算法转化为在MapReduce范式中高效工作？有没有现有的图书馆可以做这类事情？

Answer 1

MapReduce是一个并行化框架，因此算法在一定程度上必须易于并行化，即我们可以将解空间的处理划分为独立的集合。我想，对于天真算法，你可以告诉每个节点找到以固定图节点开始的k-1长路径。为了简单起见，如果我们有n个机器，它们中的每一个都可以搜索以1，2，…开始的k-1路径。。。，n.当然，并行化只能不断地提高时间。