Parameterized counting of trees, forests and matroid bases

DOI10.1007/978-3-319-58747-9_10zbMATH Open1489.68175arXiv1611.01823OpenAlexW2553008661MaRDI QIDQ2399367FDOQ2399367

Cornelius Brand, Marc Roth

Publication date: 22 August 2017

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Parameterized Algorithms
• Deterministic Truncation of Linear Matroids
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Bicycle dimension and special points of the Tutte polynomial
• A parameterized view on matroid optimization problems
• Counting trees in a graph is \(\# \text{P}\)-complete
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
• Counting Matchings of Size k Is $\sharp$ W[1]-Hard
• Counting bases of representable matroids
• Fine-grained dichotomies for the Tutte plane and Boolean #CSP
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES

Cited In (7)

• Compactors for parameterized counting problems
• Title not available (Why is that?)
• Parameterised counting in logspace
• Parameterized counting of partially injective homomorphisms
• Parameterized Counting and Cayley Graph Expanders
• Title not available (Why is that?)
• Tree-tree matrices and other combinatorial problems from taxonomy

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)