Publication Overview

Cornelius Brand and Marc Roth

Parameterized counting of trees, forests and matroid bases

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.

Published in: CSR
Year: 2017