The challenges of unbounded treewidth in parameterised subgraph counting problems

DOI10.1016/J.DAM.2015.06.019zbMATH Open1327.05244arXiv1402.5857OpenAlexW2963279056MaRDI QIDQ897601FDOQ897601

Kitty Meeks

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area. Many of the existing tractability results for parameterised problems which involve finding or counting subgraphs with particular properties rely on bounding the treewidth of these subgraphs in some sense; here, we prove a number of hardness results for the situation in which this bounded treewidth condition does not hold, resulting in dichotomies for some special cases of the general subgraph counting problem. The paper also gives a thorough survey of known results on this subject and the methods used, as well as discussing the relationships both between multicolour and uncoloured versions of subgraph counting problems, and between exact counting, approximate counting and the corresponding decision problems.

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

zbMATH Keywords

counting complexityparameterised complexitysubgraph countingFPTRAS

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Finding and counting vertex-colored subtrees
• Parametrized complexity theory.
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Complexity of Enumeration and Reliability Problems
• Color-coding
• Finding and counting given length cycles
• Graph minors. V. Excluding a planar graph
• When is the evaluation of conjunctive queries tractable?
• The Parameterized Complexity of k-B<scp>iclique</scp>
• The complexity of counting homomorphisms seen from the other side
• Counting Paths and Packings in Halves
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On the parameterized complexity of multiple-interval graph problems
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• The complexity of counting in sparse, regular, and planar graphs
• Arboricity and Subgraph Listing Algorithms
• Computational complexity of counting problems on 3-regular planar graphs
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Bounded Tree-Width and CSP-Related Problems
• Understanding the Complexity of Induced Subgraph Isomorphisms
• The Parameterized Complexity of Counting Problems
• Recognizing small subgraphs
• Parameterized circuit complexity and the \(W\) hierarchy
• Parameterized complexity of finding subgraphs with hereditary properties.
• The parameterised complexity of counting connected subgraphs and graph motifs
• Counting subgraphs via homomorphisms
• Balanced families of perfect hash functions and their applications
• Experimental and Efficient Algorithms
• Some hard families of parameterized counting problems
• Weighted Counting of k-Matchings Is #W[1]-Hard
• Parameterized random complexity
• Finding, minimizing, and counting weighted subgraphs
• Balanced Hashing, Color Coding and Approximate Counting
• Parameterized Analogues of Probabilistic Computation
• Counting Matchings of Size k Is $\sharp$ W[1]-Hard

Cited In (24)

• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Randomised enumeration of small witnesses using a decision oracle
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Counting Homomorphic Cycles in Degenerate Graphs
• Counting Small Induced Subgraphs with Hereditary Properties
• Parameterised counting in logspace
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• On the complexity of finding and counting solution-free sets of integers
• Properties of uniformly \(3\)-connected graphs
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Counting subgraphs in somewhere dense graphs
• On planar valued CSPs
• On Counting Parameterized Matching and Packing
• Title not available (Why is that?)
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Parameterized Counting and Cayley Graph Expanders
• Counting Subgraphs in Degenerate Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: The challenges of unbounded treewidth in parameterised subgraph counting problems

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