# Algorithm to compute average length of a simple path

Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?

• Are you looking for exact algorithms or are you fine with approximations of the average length? By intuition, I would say that calculating the exact average length is NP-hard (seeing as checking if there exists a Hamiltonian path is already NP-hard), but approximating it to within $[(1-\varepsilon)L, (1+\varepsilon)L]$ (where L is the solution) might be possible efficiently. Commented Jul 26, 2020 at 14:03
• @SmeltQuake Anything would be interesting. Can Hamiltonian circuit/path really be reduced to this problem? You can certainly determine if there is at least one path between s and t in poly time.
– Simd
Commented Jul 26, 2020 at 14:25
• I do not know if Hamiltonian path can be reduced to this problem. This is just an intuition about why I think the exact problem is probably NP-hard: If you cannot even determine if there exists a path of length n, calculating the average over all lengths (which also sums over the paths of length n) is probably also hard. Commented Jul 26, 2020 at 14:30
• @SmeltQuake I understood your intuition but the reduction, if it exists, is not clear to me. Hopefully someone here will see it more clearly.
– Simd
Commented Jul 26, 2020 at 14:32

Now imagine, expecting to discover a contradiction, that you could compute $$\text{avg}(G, u, v)$$ in polynomial time.
Let $$G+l$$ be the graph resulting from adding a simple path of length $$l$$ between $$u$$ and $$v$$ in $$G$$. This new path is made of $$l-1$$ new nodes and it does not interfere with any previous path from $$u$$ to $$v$$, provided $$l \geq 2$$.
Then, $$\text{avg}(G+3,u,v) - \text{avg}(G+2,u,v)$$ = $$1/(\#\text{Paths}(G,u,v)+1)$$, from which you can get $$\#\text{Paths}(G,u,v)$$ in polynomial time. But we know this cannot be expected to be done in polynomial time, a contradiction.