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?)
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 or $O^*(2.62^k)$ deterministically.
This is while Counting $k$-paths is $\#W[1]$-hard.
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 as well !