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={<G> | 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 , k> | 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.

  • 2
    $\begingroup$ 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. $\endgroup$ Dec 28, 2023 at 13:04
  • $\begingroup$ "has $k$ simple paths..." do you mean exactly $k$ or at least $k$? $\endgroup$
    – Neal Young
    Dec 29, 2023 at 0:12
  • 1
    $\begingroup$ (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. $\endgroup$ Dec 30, 2023 at 10:39


Your Answer

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