<p>I learned that &quot;counting the simple paths in a graph(whether directed or not)&quot; is <strong>#P-Complete</strong>.</p>
<p>I'm wondering what the complexity is for its decision version.</p>
<p>Here are two types I'm considering:</p>
<p>1.L={&lt;G&gt; | There exists a simple path between s and t} (s,t are two special points. s is the start, t is the end)</p>
<p>2.L={&lt;G , k&gt; | G has k simple paths between s and t}</p>
<p>Traditionally, it seems that the type 1 is the decision version of the counting problem (and it's in <strong>P</strong> obviously), but I'm extremely curious about the second one.</p>

CC BY-SA 4.0
2023-12-28T13:04:41.673Z
Well, 1 is just the s-t-connectivity problem, which is (SL =) L-complete or NL-complete, depending on whether the graph is undirected or directed.
Emil Jeřábek
CC BY-SA 4.0
2023-12-29T00:12:03.180Z
"has $k$ simple paths..." do you mean *exactly* $k$ or *at least* $k$?
Neal Young
CC BY-SA 4.0
2023-12-30T10:39:32.343Z
(Now that I've seen Valiant's reduction, I'll rephrase my comments.) Problem 2 is ambiguous; the natural upper bounds (that work for arbitrary counting problems) are $\mathrm C_=$ for the "exactly $k$" reading with $k$ given in binary, PP for "at least $k$" with $k$ in binary, US for "exactly $k$" with $k$ in unary, and NP for "at least $k$" with $k$ unary. The original reduction showing #P-completeness can be adapted to show that the "at least $k$" version with $k$ in binary is PP-complete, but it's not clear to me whether the remaining three versions are complete for the respective classes.
Emil Jeřábek
<cc.complexity-theory><np-hardness><time-complexity>
What's the complexity of the "decision version" of counting the paths in a graph?
Wenhao Wu
# What's the complexity of the "decision version" of counting the paths in a graph?

(Asked by: username_0 on 2023-12-28)

I learned that "counting the simple paths in a graph(whether directed or not)" is **#P-Complete**.

I'm wondering what the complexity is for its decision version.

Here are two types I'm considering:

1.L={ | There exists a simple path between s and t} (s,t are two special points. s is the start, t is the end)

2.L={ | G has k simple paths between s and t}

Traditionally, it seems that the type 1 is the decision version of the counting problem (and it's in **P** obviously), but I'm extremely curious about the second one.

**Tags:** cc.complexity-theory, np-hardness, time-complexity
> **Comments:**
> **username_1**: Well, 1 is just the s-t-connectivity problem, which is (SL =) L-complete or NL-complete, depending on whether the graph is undirected or directed.  
> **username_2**: "has $k$ simple paths..." do you mean *exactly* $k$ or *at least* $k$?  
> **username_1**: (Now that I've seen Valiant's reduction, I'll rephrase my comments.) Problem 2 is ambiguous; the natural upper bounds (that work for arbitrary counting problems) are $\mathrm C_=$ for the "exactly $k$" reading with $k$ given in binary, PP for "at least $k$" with $k$ in binary, US for "exactly $k$" with $k$ in unary, and NP for "at least $k$" with $k$ unary. The original reduction showing #P-completeness can be adapted to show that the "at least $k$" version with $k$ in binary is PP-complete, but it's not clear to me whether the remaining three versions are complete for the respective classes.  

---

## 0 answers

