17
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.