# Counting the Number of Simple Paths in Undirected Graph

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.

• This has been asked already on mathoverflow: mathoverflow.net/questions/18603/… Dec 18, 2013 at 20:16
• Actually, the question at mathoverflow was about finding all paths, and not counting them. Finding them can be a lot harder. Dec 19, 2013 at 13:57
• 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. Jan 18, 2017 at 13:30

## 3 Answers

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.

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". Journal of Graph Algorithms and Applications, 11(1):195-214, 2007.

L. G. Valiant, "The complexity of enumeration and reliability problems". SIAM Journal on Computing 8(3):410-421, 1979.

• The Roberts and Kroese paper does not seem to give approximation guarantees. Is there a PTAS known for this problem? Dec 19, 2013 at 6:20
• @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}!$. May 21, 2017 at 0:34

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 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)})$.