The challenges of unbounded treewidth in parameterised subgraph counting problems
From MaRDI portal
Publication:897601
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 139776 (Why is no real title available?)
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- Arboricity and Subgraph Listing Algorithms
- Balanced families of perfect hash functions and their applications
- Balanced hashing, color coding and approximate counting
- Bounded Tree-Width and CSP-Related Problems
- Color-coding
- Computational complexity of counting problems on 3-regular planar graphs
- Counting Paths and Packings in Halves
- Counting matchings of size \(k\) is \#W[1]-hard
- Counting subgraphs via homomorphisms
- Efficient triangle counting in large graphs via degree-based vertex partitioning
- Experimental and Efficient Algorithms
- Finding and counting given length cycles
- Finding and counting vertex-colored subtrees
- Finding, minimizing, and counting weighted subgraphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. V. Excluding a planar graph
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- On the parameterized complexity of multiple-interval graph problems
- Parameterized analogues of probabilistic computation
- Parameterized circuit complexity and the \(W\) hierarchy
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized random complexity
- Parametrized complexity theory.
- Recognizing small subgraphs
- Some hard families of parameterized counting problems
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- The Complexity of Enumeration and Reliability Problems
- The Parameterized Complexity of Counting Problems
- The Spatial Complexity of Oblivious k-Probe Hash Functions
- The complexity of counting homomorphisms seen from the other side
- The complexity of counting in sparse, regular, and planar graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The parameterised complexity of counting connected subgraphs and graph motifs
- The parameterized complexity of \(k\)-biclique
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Weighted counting of \(k\)-matchings is \#W[1]-hard
- When is the evaluation of conjunctive queries tractable?
Cited in
(24)- Counting Unlabelled Subtrees of a Tree is #P-complete
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- The complexity of pattern counting in directed graphs, parameterised by the outdegree
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Randomised enumeration of small witnesses using a decision oracle
- Counting Subgraphs in Degenerate Graphs
- Parameterised counting in logspace
- On planar valued CSPs
- Counting connected subgraphs with maximum-degree-aware sieving
- On Counting Parameterized Matching and Packing
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Properties of uniformly \(3\)-connected graphs
- Parameterized Counting and Cayley Graph Expanders
- Counting problems in parameterized complexity
- Counting Homomorphic Cycles in Degenerate Graphs
- Counting Small Induced Subgraphs with Hereditary Properties
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- On the complexity of finding and counting solution-free sets of integers
- Counting subgraphs in somewhere dense graphs
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
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)
