Counting Small Induced Subgraphs Satisfying Monotone Properties

DOI10.1137/20M1365624OpenAlexW3017256250MaRDI QIDQ5071087

Philip Wellnitz, Johannes Schmitt, Marc Roth

Publication date: 20 April 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphsgraph homomorphismsparameterized complexitycounting complexityfine-grained complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of commutative algebra (05E40) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• Structural tractability of counting of solutions to conjunctive queries
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• The complexity of counting homomorphisms seen from the other side
• Girth and treewidth
• Lower bound of the Hadwiger number of graphs by their average degree
• Counting induced subgraphs: a topological approach to \#W[1-hardness]
• Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness]
• The strong perfect graph theorem
• Strong computational lower bounds via parameterized complexity
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• A topological approach to evasiveness
• Ramsey's theorem - a new lower bound
• Counting \(H-\)colorings of partial \(k-\)trees
• The parameterised complexity of counting even and odd induced subgraphs
• The extremal function for complete minors
• Parameterized complexity of finding subgraphs with hereditary properties.
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• The parameterised complexity of counting connected subgraphs and graph motifs
• A fixed-parameter perspective on \#BIS
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• On a property of the class of n-colorable graphs
• Tight lower bounds for certain parameterized NP-hard problems
• Some Hard Families of Parameterized Counting Problems
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems
• The statistics of dimers on a lattice
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• PP is as Hard as the Polynomial-Time Hierarchy
• Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• An Algorithm for Subgraph Isomorphism
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Counting Answers to Existential Questions
• When is the evaluation of conjunctive queries tractable?
• Approximating Pairwise Correlations in the Ising Model
• Dimer problem in statistical mechanics-an exact result
• Paths, Trees, and Flowers
• Parameterized Algorithms
• The complexity of theorem-proving procedures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
• Transactions on Computational Systems Biology III
• On Hermite-Birkhoff interpolation
• On the complexity of \(k\)-SAT

This page was built for publication: Counting Small Induced Subgraphs Satisfying Monotone Properties