# Average length of s-t (simple) paths in a directed graph

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.

• If paths are allowed to revisit vertices, then a non-simple $s-t$ path implies that there is no average length, as the length will tend to infinity. Apr 8, 2013 at 18:31
• @Shaull, you are right. I was thinking of the hitting time of a random walk from $s$ to $t$. But the average length does tend to infinity without further constraints. Apr 8, 2013 at 18:42
• this seems to be very advanced, recommend migrate to cstheory
– vzn
Apr 9, 2013 at 4:10
• If I understand right, this question might be of interest to you for a special graph.
– Juho
Apr 9, 2013 at 4:29
• seems like this might be related to max network flow? also note for small world graphs and various other graphs with some symmetry, it will tend toward the average path length. a fairly natural algorithm might be to randomly sample shortest $s$-$t$ paths and look at the standard deviation of results.
– vzn
Apr 10, 2013 at 2:22

• Thanks for the comment and the references. I came up with this problem when trying to model the workload of a query processing system with probabilistic graph. The graph model does have some unique properties that lead me to believe that there might be an approximation of the average length $s$-$t$ paths. As suggested in your comment, random sampling does give an approximation. Problem is that it does not give a guaranteed upper bound of the approximation, except the length of the longest $s$-$t$ path. Worse still, computing the longest $s$-$t$ path itself is a NP-complete problem. Apr 10, 2013 at 7:27