Counting Small Induced Subgraphs with Hereditary Properties

DOI10.1137/22M1512211MaRDI QIDQ6154192zbMATH OpenOpenAlexFDO

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

counting complexityfine-grained complexitygraph homomorphismshereditary propertiesinduced subgraphsparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

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

Cited in

(3)

• Can you link up with treewidth?
• Counting small induced subgraphs: scorpions are easy but not trivial
• Can you link up with treewidth?

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)