<p>There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.345">Vassilevska and Williams, 2009</a>.</p>

CC BY-SA 3.0
2013-12-19T09:21:03.707Z
2013-12-19T09:21:03.707Z
Andreas Björklund
<p>It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007).</p>

<hr>

<p>B. Roberts and D. P. Kroese, "<a href="http://jgaa.info/accepted/2007/RobertsKroese2007.11.1.pdf">Estimating the number of $s$--$t$ paths in a graph</a>". <em>Journal of Graph Algorithms and Applications</em>, 11(1):195-214, 2007.</p>

<p>L. G. Valiant, "<a href="http://epubs.siam.org/doi/abs/10.1137/0208032">The complexity of enumeration and reliability problems</a>". <em>SIAM Journal on Computing</em> 8(3):410-421, 1979.</p>

CC BY-SA 3.0
2013-12-19T06:20:41.843Z
The Roberts and Kroese paper does not seem to give approximation guarantees. Is there a PTAS known for this problem?
Sasho Nikolov
CC BY-SA 3.0
2017-05-21T00:34:17.353Z
@SashoNikolov, it seems unlikely that there is any reasonable approximation algorithm.  Given $G=(V,E)$ obtain $G'$ from $G$ by replacing each node by a clique of size $N=n^c$ where $n=|V|$ and $c\gg 1$.  For each simple path of length $\ell$ in $G$ there are roughly $(N!)^\ell$ paths in $G'$.  So if $G$ has an $s-t$ Hamiltonian path, there will be at least $(N!)^{n}$ or so simple $s-t$ paths in $G'$, and otherwise at most something like $(n-1)!(N!)^{n-1}$ simple $s-t$ paths.  So it should be hard to approximate within a factor of about $N!/(n-1)! \gg n^{c-1}!$.
Neal Young
CC BY-SA 3.0
2013-12-18T22:27:04.893Z
2013-12-18T22:27:04.893Z
David Richerby
<p>I'd like to add another approximation algorithm, a parametrized one:
For a fixed $\delta&gt;0$ (or more preciesly, $\delta =\Omega(\frac{1}{poly(k)})$ ),  <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=918B7428BAD06428C58DFF7CEF62BEBE?doi=10.1.1.146.408&amp;rep=rep1&amp;type=pdf" rel="nofollow">you can compute</a> a $(1+\delta)$-approximation of the number of simple paths, in either undirected or directed graph, of length $k$ in time $O^*(2^{O(k)})$.</p>

CC BY-SA 3.0
2014-02-27T18:12:58.943Z
2014-07-30T13:03:14.803Z
2014-07-30T13:03:14.803Z
R B
<p>How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.</p>

<p>Recall that a simple path is a path with no cycles, so I'm talking about counting the number of paths with no cycle.</p>

CC BY-SA 3.0
2013-12-18T20:16:34.767Z
This has been asked already on mathoverflow: http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph
Listing
CC BY-SA 3.0
2013-12-19T13:57:02.837Z
Actually, the question at mathoverflow was about finding all paths, and not counting them. Finding them can be a lot harder.
DCTLib
CC BY-SA 3.0
2017-01-18T13:30:28.573Z
Beside the references that are given in the answers, one trivial observation is that if one can count number of paths of length $n-1$ then can answer the question of existence of a hamiltonian path. So most likely it is not P.
Saeed
<graph-theory><co.combinatorics><counting-complexity>
Counting the Number of Simple Paths in Undirected Graph
Ryan
# Counting the Number of Simple Paths in Undirected Graph

(Asked by: username_0 on 2013-12-18)

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths.

Recall that a simple path is a path with no cycles, so I'm talking about counting the number of paths with no cycle.

**Tags:** graph-theory, co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: This has been asked already on mathoverflow: http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph  
> **username_2**: Actually, the question at mathoverflow was about finding all paths, and not counting them. Finding them can be a lot harder.  
> **username_3**: Beside the references that are given in the answers, one trivial observation is that if one can count number of paths of length $n-1$ then can answer the question of existence of a hamiltonian path. So most likely it is not P.  

---

## 3 answers

### Answer by username_4 on 2013-12-19. Score: 21

There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. [Vassilevska and Williams, 2009](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.345).


---

### Answer by username_5 on 2013-12-18. Score: 20

It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007).

---

B. Roberts and D. P. Kroese, "[Estimating the number of $s$--$t$ paths in a graph](http://jgaa.info/accepted/2007/RobertsKroese2007.11.1.pdf)". *Journal of Graph Algorithms and Applications*, 11(1):195-214, 2007.

L. G. Valiant, "[The complexity of enumeration and reliability problems](http://epubs.siam.org/doi/abs/10.1137/0208032)". *SIAM Journal on Computing* 8(3):410-421, 1979.

> **Comments:**
> **username_6**: The Roberts and Kroese paper does not seem to give approximation guarantees. Is there a PTAS known for this problem?  
> **username_7**: @SashoNikolov, it seems unlikely that there is any reasonable approximation algorithm.  Given $G=(V,E)$ obtain $G'$ from $G$ by replacing each node by a clique of size $N=n^c$ where $n=|V|$ and $c\gg 1$.  For each simple path of length $\ell$ in $G$ there are roughly $(N!)^\ell$ paths in $G'$.  So if $G$ has an $s-t$ Hamiltonian path, there will be at least $(N!)^{n}$ or so simple $s-t$ paths in $G'$, and otherwise at most something like $(n-1)!(N!)^{n-1}$ simple $s-t$ paths.  So it should be hard to approximate within a factor of about $N!/(n-1)! \gg n^{c-1}!$.  

---

### Answer by username_8 on 2014-02-27. Score: 7

I'd like to add another approximation algorithm, a parametrized one:
For a fixed $\delta>0$ (or more preciesly, $\delta =\Omega(\frac{1}{poly(k)})$ ), [you can compute](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=918B7428BAD06428C58DFF7CEF62BEBE?doi=10.1.1.146.408&rep=rep1&type=pdf) a $(1+\delta)$-approximation of the number of simple paths, in either undirected or directed graph, of length $k$ in time $O^\*(2^{O(k)})$.


---

