Алгоритм вычисления средней длины простого пути

Question

Учитывая связный граф и две вершины s и t, может быть много различных простых путей (без циклов) от s до t.Существует ли эффективный алгоритм для определения средней длины этих путей?

Answer 1

Я думаю, вы уже знаете, что полиномиальный алгоритм для подсчета количества простых путей между двумя узлами подразумевал бы P = NP, этот результат получен благодаря Valiant (The complexity of enumeration and reliability problems, 1979).

Теперь представьте, что вы ожидаете обнаружить противоречие, которое вы могли бы вычислить $\текст{среднее значение}(G, u, v)$ за полиномиальное время.

Пусть $G+l$ быть графиком, полученным в результате добавления простого пути длины $l$ между $u$ и $v$ в $G$.Этот новый путь состоит из $l-1$ новые узлы, и это не мешает никакому предыдущему пути от $u$ Для $v$, предоставленный $l \ geq 2$.

Тогда, $ ext{среднее значение}(G+3,u,v) - ext{среднее значение}(G+2,u,v)$ = $1/(\#\текст{Пути}(G,u,v)+1)$, из которого вы можете получить $\#\текст{Пути}(G,u,v)$ за полиномиальное время.Но мы знаем, что нельзя ожидать, что это будет сделано за полиномиальное время, что является противоречием.