Поиск путей длины k

Question

Учитывая график с n узлами, существует ряд последовательных методов повышения сложности и уменьшения сложности поиска простых путей длины k в графе. Самая известная асимптотическая сложность в настоящее время составляет O(2^k poly(n,k)) time. С другой стороны, наивный алгоритм просто перечисляет все пути длины k и принимает O (n^k) время (по крайней мере).

Как вы могли бы перевести наивный алгоритм для эффективной работы в парадигме MapReduce? Существуют ли библиотеки для такого рода вещей?

Answer 1

MapReduce - это структура параллелизации, поэтому алгоритм должен быть в некоторой степени восприимчивым к параллелизации, то есть мы можем разделить обработку пространства решения на независимые множества. Я предполагаю, что для наивного алгоритма вы можете указать каждому узлу найти k-1 длинные пути, которые начинаются с фиксированного узла графа. Для простоты, если у нас есть n машин, каждый из них может искать пути k-1, начинающиеся с 1, 2, ..., n. Конечно, параллелизация дает только постоянное улучшение времени.