<p>This problem should be NP-hard by reducing from the maximum length of s-t paths. </p>

<p>The reduction simply replace every edge by, say, <span class="math-container">$k$</span> 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 <span class="math-container">$C_{\ell}$</span> of paths of length <span class="math-container">$\ell$</span> becomes <span class="math-container">$k^\ell C_{\ell}$</span>. Thus, if <span class="math-container">$k$</span> is suitably large, the term corresponding to the longest paths in the original graph will dominate everything else (even if <span class="math-container">$C_{\ell_{max}}=1$</span>). From there you can easily recover the length of the longest s-t path.</p>

CC BY-SA 4.0
2019-04-12T05:44:19.653Z
2019-04-12T05:44:19.653Z
Heng Guo
<p>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?</p>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2012-11-26T22:11:37.507Z
@bbejot: See [How hard is counting the number of simple paths between two nodes in a directed graph?](http://cs.stackexchange.com/questions/423/how-hard-is-counting-the-number-of-simple-paths-between-two-nodes-in-a-directed) The only answer, by jmad, provides a link to a paper that provides indeed a random approximation
Carlos Linares López
<ds.algorithms><reference-request><graph-algorithms><approximation-algorithms><counting-complexity>
Approximation for counting the number of simple $s$-$t$ paths in a general graph
bbejot
# Approximation for counting the number of simple $s$-$t$ paths in a general graph

(Asked by: username_0 on 2011-05-04)

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.

**Tags:** ds.algorithms, reference-request, graph-algorithms, approximation-algorithms, counting-complexity

> **Comments:**
> **username_1**: @username_0: See [How hard is counting the number of simple paths between two nodes in a directed graph?](http://cs.stackexchange.com/questions/423/how-hard-is-counting-the-number-of-simple-paths-between-two-nodes-in-a-directed) The only answer, by jmad, provides a link to a paper that provides indeed a random approximation  

---

## 1 answers

### Answer by username_2 on 2019-04-12. Score: 1

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.


---

