Parameterized counting of trees, forests and matroid bases

DOI10.1007/978-3-319-58747-9_10MaRDI QIDQ2399367zbMATH OpenOpenAlexFDO

Authors Cornelius Brand, Marc Roth

Publication date 22 August 2017

Full work available at URL https://arxiv.org/abs/1611.01823

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of matroids and geometric lattices (05B35) Parameterized complexity, tractability and kernelization (68Q27)

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 $$-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 $$-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.

Recommendations

• Some problems on approximate counting in graphs and matroids
• Counting matchings of size \(k\) is \#W[1]-hard
• Some hard families of parameterized counting problems
• Counting trees in a graph is \(\# \text{P}\)-complete
• Counting the leaves of trees

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• A parameterized view on matroid optimization problems
• Bicycle dimension and special points of the Tutte polynomial
• Counting bases of representable matroids
• Counting matchings of size \(k\) is \#W[1]-hard
• Counting trees in a graph is \(\# \text{P}\)-complete
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
• Parameterized algorithms
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The Computational Complexity of the Tutte Plane: the Bipartite Case

Cited in

(8)

• scientific article; zbMATH DE number 409493 (Why is no real title available?)
• Compactors for parameterized counting problems
• Parameterized counting of partially injective homomorphisms
• Parameterised counting in logspace
• Parameterized Counting and Cayley Graph Expanders
• Counting problems in parameterized complexity
• Tree-tree matrices and other combinatorial problems from taxonomy
• Some problems on approximate counting in graphs and matroids

This page was built for publication: Parameterized counting of trees, forests and matroid bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399367)