# Approximation for counting the number of simple $s$-$t$ paths in a general graph

I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does anyone know of a good reference on this subject?

Background: counting the exact number of paths in a general graph is #P-complete but there may exist polynomial time approximations for the problem. I'm especially interested in random approximations.

Not sure if this helps, but you could use Balanced Families of Perfect Hash to approximate the number of simple paths of length $k$ in $2^{O(klogk)}$ which might be useful if you're looking for counting short paths. –  R B Jan 19 at 16:47