12
$\begingroup$

Given a directed graph with n nodes such that each vertex has exactly two outgoing edges, and a natural number N encoded in binary, two vertices s and t,

I want to count the number of (not necessarily simple) paths from s to t within N steps.

Is this a #P-hard problem? Or generally, what's the complexity of this problem?

$\endgroup$
  • 6
    $\begingroup$ Did you try matrix powering? $\endgroup$ – Yuval Filmus Jul 30 '12 at 22:02
  • 1
    $\begingroup$ yes, but the complexity is still not known as far as I can see. $\endgroup$ – maomao Jul 30 '12 at 22:12
  • $\begingroup$ Does the walk have to end at t or just visit t at some point in the walk? $\endgroup$ – Tyson Williams Aug 6 '12 at 12:35
  • $\begingroup$ it has to end up at t. $\endgroup$ – maomao Aug 6 '12 at 19:22
  • 1
    $\begingroup$ @Geekster For the complete digraph on 3 vertices with $s \ne t$, the count is the Nth Fibonacci number, the size of which is exponential in N, just as David has argued in his answer for any graph. $\endgroup$ – Tyson Williams Aug 9 '12 at 22:49
13
$\begingroup$

The output number of paths may be $\Omega(2^N/n)$ (choose $s$ arbitrarily and then choose $t$ as the vertex that is the endpoint of the largest number of the $2^N$ walks from $s$) which requires $\Omega(N)$ bits to write down explicitly; this is exponential in the input size. On the other hand, the matrix powering approach has complexity polynomial in the sum of the input and output sizes. So that seems to place it squarely in the class of counting problems that have exponential-sized output and may be solved deterministically in time polynomial in their output size, whatever the notation for that class is (it's some sort of counting analogue for EXP, and definitely not #EXP which is more analogous to NEXP).

$\endgroup$
  • 1
    $\begingroup$ thanks, but I still want to know whether this problem is $\sharp P$-hard. $\endgroup$ – maomao Aug 6 '12 at 19:29
  • 1
    $\begingroup$ To avoid the large numbers in David's iterated squaring approach, we can do all computation modulo a prime number p. Then the overall algorithm runs in time polynomial in $n + \log N + \log p$. If the problem was #P-hard under polynomial-time parsimonious many-one reductions, the algorithm with $p=2$ would imply P=$\oplus$P, which we don't believe. $\endgroup$ – Holger Oct 29 '15 at 20:54
  • $\begingroup$ @Holger wouldn't a similar argument hold for the Permanent? i.e. if Permanent is #P-hard then Perm mod 2 would be $\oplus$P hard. But Perm mod 2 = Det mod 2 which is in P. $\endgroup$ – SamiD Dec 2 '15 at 2:17
  • $\begingroup$ @SamiD: Exactly, your argument shows that the permanent is probably not #P-hard under parsimonious reductions. The known proofs use Turing reductions. $\endgroup$ – Holger Dec 2 '15 at 6:38
  • $\begingroup$ @Holger I agree. Sorry I had missed the parsimonious many-one part. Thus matrix powering powering problem may well be #P-hard under Turing reductions. $\endgroup$ – SamiD Dec 2 '15 at 6:54
4
$\begingroup$

Finding a bit of $A^N[s,t]$ where $A$ is the adjacency matrix of the given graph reduces to the problem $\mathsf{BitSLP}$ defined first in [ABKPM] which has a $\#\mathsf{P}$ lower bound established in the same paper. However whether the reduction in the reverse direction holds, i.e. from $\mathsf{BitSLP}$ to the matrix powering problem, is open AFAIK.

Notice that $\mathsf{BitSLP}$ sits squarely inside the counting hierarchy $\mathsf{CH} \subseteq \mathsf{PSPACE}$. The best known upper bound on this problem viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$ is from here.

$\endgroup$
1
$\begingroup$

The problem is #P-complete. Look at the problem of counting shortest paths in a graph (ND31 in Garey&Johnson) which is #P-complete for the counting version. Read carefully the comment. This gives the answer for paths of length $\leq N$. To get the answer for paths of length $=N$, call the shortest paths problem for $\leq N$ and $\leq N-1$, then subtract the latter from the former, i.e. perform a subtractive reduction.

Since the reduction from #HAMILTONIAN PATHS / CIRCUITS to #SHORTEST PATHS works also for 3-regular graphs, the #P-completeness result will work also for your restriction of digraphs with out-degree $\leq 2$.

$\endgroup$
  • 2
    $\begingroup$ The original problem does not require the path to be simple, so I do not think the answer is correct. $\endgroup$ – maomao Aug 6 '12 at 19:26
  • 3
    $\begingroup$ How can it be #P-complete when all #P problems have numbers of solutions which are exponential in the input size and this one is double exponential? $\endgroup$ – David Eppstein Aug 6 '12 at 20:02
  • $\begingroup$ What does "ND31" mean in the context of Garey and Johson's book? $\endgroup$ – Tyson Williams Aug 9 '12 at 22:52

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.