Algoritmo per calcolare la media lunghezza di un semplice percorso

Question

Dato un grafico collegato e due nodi s e T, possono esserci molti percorsi semplici diversi (senza cicli) da s a t.C'è un algoritmo efficiente per trovare la lunghezza media di questi percorsi?

Answer 1

Immagino che tu sappia già che un algoritmo polinomiale per il conteggio del numero di percorsi semplici tra due nodi implicherebbe P= NP, questo risultato è dovuto a Valiant (la complessità dei problemi di enumerazione e affidabilità, 1979).

Ora immagina, aspettando di scoprire una contraddizione, che potresti calcolare $ \ text {avg} (g, u, v) $ in tempo polinomiale. .

Let $ G + L $ Sii il grafico derivante dall'aggiunta di un semplice percorso di lunghezza $ l $ tra $ U $ e $ V $ in $ g $ . Questo nuovo percorso è realizzato in $ L-1 $ Nuovi nodi e non interferisce con qualsiasi percorso precedente da $ U $ a $ V $ , fornito $ l \ geq 2 $ .

quindi, $ \ text {avg} (G + 3, u, v) - \ text {avg} (G + 2, u, v) $ = $ 1 / (\ # \ testo {percorsi} (g, u, v) +1) $ , da cui è possibile ottenere $ \ # \ testo {percorsi} (g, u, v) $ in tempo polinomiale. Ma sappiamo che questo non ci si può aspettare che sia fatto in tempo polinomiale, una contraddizione.