Parameterized Counting of Trees, Forests and Matroid Bases

摘要

We prove #W[1]-hardness of counting (1) trees with k edges in a given graph, (2) forests with k edges in a given graph, and (3) bases of a given matroid of rank (or nullity) k representabte over an arbitrary field of characteristic two, where k is the parameter.