Algorithm to compute average length of a simple path

Question

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?

Answer 1

I guess you already know that a polynomial algorithm for counting the number of simple paths between two nodes would imply P=NP, this result is due to Valiant (The complexity of enumeration and reliability problems, 1979).

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.