Some hard families of parameterized counting problems

DOI10.1145/2786017MaRDI QIDQ2832302zbMATH OpenOpenAlexFDO

Authors Kitty Meeks, Mark 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, http://eprints.gla.ac.uk/97129/1/97129.pdf

Mathematics Subject Classification ID

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

Abstract: We consider parameterised subgraph-counting problems of the following form: given a graph G, how many k-tuples of its vertices have a given property? A number of such problems are known to be #W[1]-complete; here we substantially generalise some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of k-vertex subgraphs having any property where the number of distinct edge-densities of labelled subgraphs that satisfy the property is o(k^2). In the special case that the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result which leads to our second family of hard problems.

Recommendations

• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• The parameterised complexity of counting even and odd induced subgraphs

Cites work

• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• Counting matchings of size \(k\) is \#W[1]-hard
• On the parameterized complexity of multiple-interval graph problems
• Parametrized complexity theory.
• The Parameterized Complexity of Counting Problems
• The complexity of counting homomorphisms seen from the other side
• The parameterised complexity of counting connected subgraphs and graph motifs

Cited in

(16)

• Compactors for parameterized counting problems
• Randomised enumeration of small witnesses using a decision oracle
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting Small Induced Subgraphs with Hereditary Properties
• Counting problems in parameterized complexity
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Parameterized counting of trees, forests and matroid bases
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting connected subgraphs with maximum-degree-aware sieving
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Counting matchings of size \(k\) is \#W[1]-hard
• Parameterized Counting and Cayley Graph Expanders
• The Parameterized Complexity of Counting Problems

This page was built for publication: Some hard families of parameterized counting problems

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