<p>Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in <a href="http://arxiv.org/pdf/0807.3026.pdf">$O^*(2^k)$ with a randomized algorithm</a> or <a href="http://www.cs.technion.ac.il/~hadas/PUB/REPFAM_SZ.pdf">$O^*(2.62^k)$ deterministically</a>.</p>

<p>This is while <a href="http://web.stanford.edu/~rrwill/presentations/counting-k-paths.pdf">Counting $k$-paths is $\#W[1]$-hard</a>.</p>

<hr>

<p>A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
Not only that the problem is $\#P$-complete, it was recently shown to be <a href="http://arxiv.org/abs/1407.2929">$\#W[1]$-hard</a> as well !</p>

CC BY-SA 3.0
2015-04-14T07:01:04.630Z
2015-04-14T08:15:37.000Z
2015-04-14T08:15:37.000Z
R B
<p>It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P.
Is there a problem, that exhibits the same behavior in parametrized  complexity? (Decision in FPT and counting in #W[1] or some other counting class?) </p>

<cc.complexity-theory><complexity-classes><counting-complexity><parameterized-complexity><fixed-parameter-tractable>
Easy decision hard counting Parametrized
Paramar
# Easy decision hard counting Parametrized

(Asked by: username_0 on 2015-04-14)

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P.
Is there a problem, that exhibits the same behavior in parametrized complexity? (Decision in FPT and counting in #W[1] or some other counting class?)

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, parameterized-complexity, fixed-parameter-tractable


---

## 1 answers

### Answer by username_1 on 2015-04-14. Score: 10 | Accepted answer

Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in [$O^\*(2^k)$ with a randomized algorithm](http://arxiv.org/pdf/0807.3026.pdf) or [$O^\*(2.62^k)$ deterministically](http://www.cs.technion.ac.il/~hadas/PUB/REPFAM_SZ.pdf).

This is while [Counting $k$-paths is $\#W[1]$-hard](http://web.stanford.edu/~rrwill/presentations/counting-k-paths.pdf).

---

A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
Not only that the problem is $\#P$-complete, it was recently shown to be [$\#W[1]$-hard](http://arxiv.org/abs/1407.2929) as well !


---

