Parameterized counting of trees, forests and matroid bases

Abstract

We investigate the complexity of counting trees, forests and bases of matroids from a parameterized point of view. It turns out that the problems of computing the number of trees and forests with $k$ edges are $\#W[1]$-hard when parameterized by $k$. Together with the recent algorithm for deterministic matrix truncation by Lokshtanov et al. (ICALP 2015), the hardness result for $k$-forests implies $\#W[1]$-hardness of the problem of counting bases of a matroid when parameterized by rank or nullity, even if the matroid is restricted to be representable over a field of characteristic $2$. We complement this result by pointing out that the problem becomes fixed parameter tractable for matroids represented over a fixed finite field.

14 pages