Some Hard Families of Parameterized Counting Problems

DOI10.1145/2786017zbMath1348.68066arXiv1310.6524OpenAlexW2964347561MaRDI QIDQ2832302

Kitty Meeks, Mark R. Jerrum

Publication date: 10 November 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness]

Cites Work

• Unnamed Item
• The complexity of counting homomorphisms seen from the other side
• On the parameterized complexity of multiple-interval graph problems
• The parameterised complexity of counting connected subgraphs and graph motifs
• Parametrized complexity theory.
• The Parameterized Complexity of Counting Problems
• Counting Matchings of Size k Is $\sharp$ W[1-Hard]