6
$\begingroup$

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

$\endgroup$

1 Answer 1

10
$\begingroup$

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 !

$\endgroup$

Your Answer

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