The challenges of unbounded treewidth in parameterised subgraph counting problems

DOI10.1016/j.dam.2015.06.019zbMath1327.05244arXiv1402.5857OpenAlexW2963279056MaRDI QIDQ897601

Kitty Meeks

Publication date: 7 December 2015

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

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

zbMATH Keywords

counting complexityparameterised complexitysubgraph countingFPTRAS

Mathematics Subject Classification ID

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

Related Items

Counting Subgraphs in Degenerate Graphs, 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, On planar valued CSPs, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Counting Homomorphic Cycles in Degenerate Graphs, Parameterised counting in logspace, 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, On Counting Parameterized Matching and Packing, On the complexity of finding and counting solution-free sets of integers, Unnamed Item, Unnamed Item, Unnamed Item, Counting edge-injective homomorphisms and matchings on restricted graph classes, Counting induced subgraphs: a topological approach to \#W[1-hardness]

Cites Work

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