Counting Small Induced Subgraphs with Hereditary Properties
From MaRDI portal
Publication:6154192
DOI10.1137/22m1512211OpenAlexW4392748624MaRDI QIDQ6154192
Publication date: 19 March 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/22m1512211
induced subgraphsgraph homomorphismshereditary propertiesparameterized complexitycounting complexityfine-grained complexity
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Structural tractability of counting of solutions to conjunctive queries
- The complexity of counting homomorphisms seen from the other side
- Counting induced subgraphs: a topological approach to \#W[1-hardness]
- Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness]
- Strong computational lower bounds via parameterized complexity
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Triad count statistics
- The parameterised complexity of counting even and odd induced subgraphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Describing parameterized complexity classes
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- The parameterised complexity of counting connected subgraphs and graph motifs
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- Some Hard Families of Parameterized Counting Problems
- The statistics of dimers on a lattice
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Homomorphisms are a good basis for counting small subgraphs
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Approximately counting and sampling small witnesses using a colourful decision oracle
- When is the evaluation of conjunctive queries tractable?
- Dimer problem in statistical mechanics-an exact result
- Parameterized Algorithms
- Transactions on Computational Systems Biology III
- On the complexity of \(k\)-SAT
This page was built for publication: Counting Small Induced Subgraphs with Hereditary Properties
