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$
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.