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.
Thanks in advance.
This problem should be NP-hard by reducing from the maximum length of s-t paths.
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.
