20
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This has been asked already on mathoverflow: mathoverflow.net/questions/18603/… $\endgroup$
    – Listing
    Commented Dec 18, 2013 at 20:16
  • 6
    $\begingroup$ Actually, the question at mathoverflow was about finding all paths, and not counting them. Finding them can be a lot harder. $\endgroup$
    – DCTLib
    Commented Dec 19, 2013 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jan 18, 2017 at 13:30

3 Answers 3

Reset to default
21
$\begingroup$

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.

Improve this answer
$\endgroup$
0
20
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ The Roberts and Kroese paper does not seem to give approximation guarantees. Is there a PTAS known for this problem? $\endgroup$
    – Sasho Nikolov
    Commented Dec 19, 2013 at 6:20
  • 4
    $\begingroup$ @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}!$. $\endgroup$
    – Neal Young
    Commented May 21, 2017 at 0:34
7
$\begingroup$

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

Improve this answer
$\endgroup$

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