Algoritmo para calcular o comprimento médio de um caminho simples

Question

Dado um gráfico conectado e dois nós e t, pode haver muitos caminhos simples diferentes (sem ciclos) de S para t.Existe um algoritmo eficiente para encontrar o comprimento médio desses caminhos?

Answer 1

Eu acho que você já sabe que um algoritmo polinomial para contar o número de caminhos simples entre dois nós implicaria p= NP, este resultado deve-se à valente (a complexidade de problemas de enumeração e confiabilidade, 1979).

Agora imagine, esperando descobrir uma contradição, que você poderia calcular $ \ text {avg} (g, u, v) $ no tempo polinomial. .

Deixe $ g + L $ o gráfico resultante adicionando um simples caminho de comprimento $ l $ entre $ u $ e $ v $ em $ g $ . Este novo caminho é feito de $ l-1 $ nós novos e não interfere com qualquer caminho anterior da $ U $ para $ v $ , desde $ l \ geq 2 $ .

Então, $ \ text {avg} (g + 3, u, v) - \ text {avg} (g + 2, u, v) $ = $ 1 / (\ # \ text {paths} (g, u, v) +1) $ , a partir do qual você pode obter $ \ # \ text {paths} (g, u, v) $ no tempo polinomial. Mas sabemos que isso não pode ser esperado para ser feito em tempo polinômio, uma contradição.