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
    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
    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
    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
19
$\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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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