Publication Overview

Cornelius Brand and Marc Roth

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 representable over an arbitrary field of characteristic two, where k is the parameter.

Published in: Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12
Year: 2017
Pages: 85-98