Algoritmo para calcular la longitud media de un camino simple

Question

Dado un gráfico conectado y dos nodos S y T, puede haber muchos caminos simples diferentes (sin ciclos) de S a t.¿Hay un algoritmo eficiente para encontrar la longitud promedio de estos caminos?

Answer 1

Supongo que ya sabe que un algoritmo polinomial para contar el número de caminos simples entre dos nodos implicaría P= NP, este resultado se debe a valientes (la complejidad de los problemas de enumeración y fiabilidad, 1979).

Ahora imagine, esperando descubrir una contradicción, que podría computar $ \ texto {promot} (g, u, v) $ en tiempo polinomial.

Let $ G + L $ Be el gráfico resultante de agregar una ruta simple de longitud $ l $ Entre $ u $ y $ v $ en $ g $ . Esta nueva ruta está hecha de $ l-1 $ nodos nuevos y no interfiere con ninguna ruta anterior desde $ u $ a $ v $ , proporcionado $ l \ geq 2 $ .

Luego, $ \ texto {promot} (g + 3, u, v) - \ texto {promot} (g + 2, u, v) $ = $ 1 / (\ # \ texto {rutas} (g, u, u, u, v) +1) $ , desde donde puede obtener $ \ # \ texto {rutas} (g, u, v) $ en tiempo polinomial. Pero sabemos que esto no se puede esperar que se haga en el tiempo polinomial, una contradicción.