<p>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).</p>

CC BY-SA 3.0
2012-08-06T19:29:03.877Z
thanks, but I still want to know whether this problem is $\sharp P$-hard.
maomao
CC BY-SA 3.0
2015-10-29T20:54:06.407Z
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.
Holger
CC BY-SA 3.0
2015-12-02T02:17:20.303Z
@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.
SamiD
CC BY-SA 3.0
2015-12-02T06:38:35.753Z
@SamiD: Exactly, your argument shows that the permanent is probably not #P-hard under *parsimonious* reductions. The known proofs use Turing reductions.
Holger
CC BY-SA 3.0
2015-12-02T06:54:16.783Z
@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.
SamiD
CC BY-SA 3.0
2015-12-07T23:20:51.360Z
@SamiD: I'd be surprised if the matrix powering problem was #P-hard since it can be computed efficiently modulo any prime number up to poly(N), whereas the permanent is already hard modulo 3. I think the issue is entirely in the encoding length: By the Chinese remainder theorem, the number $M\le 2^N$ of paths is determined exactly by the remainders (M mod p) for the the first N or so prime numbers p; each of these remainders can be computed efficiently (but we can't efficiently compute all of them since N is exponential).
Holger
CC BY-SA 3.0
2012-07-30T22:33:27.017Z
2012-07-30T22:33:27.017Z
David Eppstein
<p>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<a href="http://ftp.cs.rutgers.edu/pub/allender/slp.pdf" rel="nofollow"> [ABKPM]</a> 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.</p>

<p>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 <a href="http://eccc.hpi-web.de/report/2013/177/" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2015-12-01T03:48:54.830Z
2016-10-30T04:46:39.670Z
2016-10-30T04:46:39.670Z
SamiD
<p>The problem is #P-complete. Look at the problem of counting shortest paths in a graph (ND31 in Garey&amp;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.</p>

<p>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$.</p>

CC BY-SA 3.0
2012-08-06T19:26:43.677Z
The original problem does not require the path to be simple, so I do not think the answer is correct.
maomao
CC BY-SA 3.0
2012-08-06T20:02:22.243Z
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?
David Eppstein
CC BY-SA 3.0
2012-08-09T22:52:58.607Z
What does "ND31" mean in the context of Garey and Johson's book?
Tyson Williams
CC BY-SA 3.0
2012-08-06T10:01:25.873Z
2012-08-06T10:01:25.873Z
Miki Hermann
<p>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, </p>

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

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

CC BY-SA 3.0
2012-07-30T22:02:59.220Z
Did you try matrix powering?
Yuval Filmus
CC BY-SA 3.0
2012-07-30T22:12:18.777Z
yes, but the complexity is still not known as far as I can see.
maomao
CC BY-SA 3.0
2012-08-06T12:35:31.683Z
Does the walk have to end at t or just visit t at some point in the walk?
Tyson Williams
CC BY-SA 3.0
2012-08-06T19:22:20.483Z
it has to end up at t.
maomao
CC BY-SA 3.0
2012-08-07T03:19:14.687Z
@maomao You an construct the graph such that there does not exists any path from s to t nor t to s. Can you give us a concrete example?  thanks
Tayfun Pay
CC BY-SA 3.0
2012-08-09T14:49:53.377Z
@Geekster What are you trying to get at? If s and t are not connected, then the count is 0.
Tyson Williams
CC BY-SA 3.0
2012-08-09T19:29:25.427Z
@Tyson I would like an example... Does not matter how many nodes. Can you give me one? Because this seems way too obvious to me, such that it can be done in P. Perhaps I am wrong.. Thanks
Tayfun Pay
CC BY-SA 3.0
2012-08-09T22:06:23.157Z
@Grekster, you can take any (nontrivial) directed graph as an example. The problem is that the number could be very large (as the answer of David suggests), so I do not know how you can achive P.
maomao
CC BY-SA 3.0
2012-08-09T22:49:12.853Z
@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.
Tyson Williams
CC BY-SA 3.0
2012-08-10T02:04:37.583Z
@maomao In the problem you stated that there are exactly two outgoing edges from each node. So it is not any directed graph.
Tayfun Pay
CC BY-SA 3.0
2012-08-10T05:12:04.630Z
@Geekster What are you saying? The complete digraph on 3 vertices has out degree 2 for each vertex.
Tyson Williams
CC BY-SA 3.0
2012-08-10T13:27:33.280Z
Correction: the count f(n) satisfies $f(n)=f(n−1)+2f(n−2)+1$, which is even larger.
Tyson Williams
CC BY-SA 3.0
2015-12-07T23:32:21.150Z
@Dror: The decision variant is poly-time. Use David's answer below, but instead of remembering the number of walks, you just store whether such a walk existed.
Holger
<cc.complexity-theory><graph-theory><counting-complexity>
Complexity of counting paths in a graph
maomao
# Complexity of counting paths in a graph

(Asked by: username_0 on 2012-07-30)

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?

**Tags:** cc.complexity-theory, graph-theory, counting-complexity

> **Comments:**
> **username_1**: Did you try matrix powering?  
> **username_0**: yes, but the complexity is still not known as far as I can see.  
> **username_2**: Does the walk have to end at t or just visit t at some point in the walk?  
> **username_0**: it has to end up at t.  
> **username_3**: @username_0 You an construct the graph such that there does not exists any path from s to t nor t to s. Can you give us a concrete example?  thanks  
> **username_2**: @Geekster What are you trying to get at? If s and t are not connected, then the count is 0.  
> **username_3**: @Tyson I would like an example... Does not matter how many nodes. Can you give me one? Because this seems way too obvious to me, such that it can be done in P. Perhaps I am wrong.. Thanks  
> **username_0**: @Grekster, you can take any (nontrivial) directed graph as an example. The problem is that the number could be very large (as the answer of David suggests), so I do not know how you can achive P.  
> **username_2**: @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.  
> **username_3**: @username_0 In the problem you stated that there are exactly two outgoing edges from each node. So it is not any directed graph.  
> **username_2**: @Geekster What are you saying? The complete digraph on 3 vertices has out degree 2 for each vertex.  
> **username_2**: Correction: the count f(n) satisfies $f(n)=f(n−1)+2f(n−2)+1$, which is even larger.  
> **username_4**: @Dror: The decision variant is poly-time. Use David's answer below, but instead of remembering the number of walks, you just store whether such a walk existed.  

---

## 3 answers

### Answer by username_5 on 2012-07-30. Score: 13

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

> **Comments:**
> **username_0**: thanks, but I still want to know whether this problem is $\sharp P$-hard.  
> **username_4**: 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.  
> **username_6**: @username_4 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.  
> **username_4**: @username_6: Exactly, your argument shows that the permanent is probably not #P-hard under *parsimonious* reductions. The known proofs use Turing reductions.  
> **username_6**: @username_4 I agree. Sorry I had missed the __parsimonious many-one__ part. Thus matrix powering powering problem may well be #P-hard under Turing reductions.  
> **username_4**: @username_6: I'd be surprised if the matrix powering problem was #P-hard since it can be computed efficiently modulo any prime number up to poly(N), whereas the permanent is already hard modulo 3. I think the issue is entirely in the encoding length: By the Chinese remainder theorem, the number $M\le 2^N$ of paths is determined exactly by the remainders (M mod p) for the the first N or so prime numbers p; each of these remainders can be computed efficiently (but we can't efficiently compute all of them since N is exponential).  

---

### Answer by username_6 on 2015-12-01. Score: 4

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]](http://ftp.cs.rutgers.edu/pub/allender/slp.pdf) 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](http://eccc.hpi-web.de/report/2013/177/).


---

### Answer by username_7 on 2012-08-06. Score: 1

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

> **Comments:**
> **username_0**: The original problem does not require the path to be simple, so I do not think the answer is correct.  
> **username_5**: 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?  
> **username_2**: What does "ND31" mean in the context of Garey and Johson's book?  

---

