Существует ли эффективный алгоритм для определения количества путей k-длины (НЕ пройденных) в неориентированном и невзвешенном графе в виде матрицы смежности?

Question

Мне известно, что число обходов k-длины между двумя вершинами можно найти, найдя k-ую степень матрицы смежности, но обходы включают в расчет обход одного ребра несколько раз.

РЕДАКТИРОВАТЬ: Я только хочу считать их не вычислить их, предпочтительно с использованием алгебры матриц.Я мог бы сделать модифицированный DFS, но это менее эффективно, чем математическая математика.

Answer 1

В общем, нет известного способа сделать это. Один из способов увидеть это состоит в том, что если вы выберете k в качестве числа узлов в графе, то вы будете запрашивать количество гамильтоновых путей в графе. Однако вопрос определения того, содержит ли граф гамильтонов путь, является канонической NP -полной проблемой, и если в P = NP нет алгоритма полиномиального времени за это.

Другими словами, задача о гамильтоновом пути сводится к вашей задаче за полиномиальное время. Это делает вашу проблему NP трудной, а это означает, что для нее нет известного алгоритма полиномиального времени.