18
$\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.

$\endgroup$
  • 2
    $\begingroup$ This has been asked already on mathoverflow: mathoverflow.net/questions/18603/… $\endgroup$ – Listing Dec 18 '13 at 20:16
  • 5
    $\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 '13 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 '17 at 13:30
20
$\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.

$\endgroup$
18
$\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.

$\endgroup$
  • 4
    $\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 '13 at 6:20
  • 3
    $\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 '17 at 0:34
6
$\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)})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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