Counting Small Induced Subgraphs with Hereditary Properties

DOI10.1137/22M1512211OpenAlexW4392748624MaRDI QIDQ6154192FDOQ6154192

Authors: Jacob Focke, Marc Roth 

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

zbMATH Keywords

graph homomorphismsinduced subgraphsparameterized complexitycounting complexityhereditary propertiesfine-grained complexity

Mathematics Subject Classification ID

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

• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Dimer problem in statistical mechanics-an exact result
• Parametrized complexity theory.
• Parameterized algorithms
• On the complexity of \(k\)-SAT
• Structural tractability of counting of solutions to conjunctive queries
• When is the evaluation of conjunctive queries tractable?
• The complexity of counting homomorphisms seen from the other side
• Title not available (Why is that?)
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Strong computational lower bounds via parameterized complexity
• Tight lower bounds for certain parameterized NP-hard problems
• Understanding the Complexity of Induced Subgraph Isomorphisms
• The parameterised complexity of counting even and odd induced subgraphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• The parameterised complexity of counting connected subgraphs and graph motifs
• Transactions on Computational Systems Biology III
• Title not available (Why is that?)
• Some hard families of parameterized counting problems
• Homomorphisms are a good basis for counting small subgraphs
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Approximately counting and sampling small witnesses using a colourful decision oracle
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Describing parameterized complexity classes
• Triad count statistics
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes

This page was built for publication: Counting Small Induced Subgraphs with Hereditary Properties

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