Some hard families of parameterized counting problems

DOI10.1145/2786017zbMATH Open1348.68066arXiv1310.6524OpenAlexW2964347561MaRDI QIDQ2832302FDOQ2832302

Authors: Kitty Meeks, Mark Jerrum 

Publication date: 10 November 2016

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

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.

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

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

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)

Cites Work

• Parametrized complexity theory.
• The complexity of counting homomorphisms seen from the other side
• On the parameterized complexity of multiple-interval graph problems
• The Parameterized Complexity of Counting Problems
• The parameterised complexity of counting connected subgraphs and graph motifs
• Title not available (Why is that?)
• Counting matchings of size \(k\) is \#W[1]-hard

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
• Counting matchings of size \(k\) is \#W[1]-hard
• Parameterized Counting and Cayley Graph Expanders
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• 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)