20

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.

D.W.
  • 12,054
  • 2
  • 34
  • 80
Ryan
  • 301
  • 1
  • 2
  • 6
  • 2
    This has been asked already on mathoverflow: http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph – Listing Dec 18 '13 at 20:16
  • 6
    Actually, the question at mathoverflow was about finding all paths, and not counting them. Finding them can be a lot harder. – DCTLib Dec 19 '13 at 13:57
  • 1
    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 Jan 18 '17 at 13:30

3 Answers3

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.

Andreas Björklund
  • 3,254
  • 1
  • 22
  • 23
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". 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.

David Richerby
  • 2,765
  • 2
  • 18
  • 28
  • 5
    The Roberts and Kroese paper does not seem to give approximation guarantees. Is there a PTAS known for this problem? – Sasho Nikolov Dec 19 '13 at 06:20
  • 4
    @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 May 21 '17 at 00:34
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 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)})$.

R B
  • 9,448
  • 5
  • 34
  • 74