# 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.

The reduction simply replace every edge by, say, $$k$$ parallel edges. (If you are uncomfortable with a multi-graph, replace each edge by a path of length 2.) The effect of this is that the number $$C_{\ell}$$ of paths of length $$\ell$$ becomes $$k^\ell C_{\ell}$$. Thus, if $$k$$ is suitably large, the term corresponding to the longest paths in the original graph will dominate everything else (even if $$C_{\ell_{max}}=1$$). From there you can easily recover the length of the longest s-t path.