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.
Approximation for counting the number of simple $s$-$t$ paths in a general graph
ds.algorithms;reference request;graph algorithms;approximation algorithms;counting complexity