Computing the number of induced copies of a fixed graph in a bounded degree graph

DOI10.1007/s00453-018-0511-9zbMath1421.68140arXiv1707.05186OpenAlexW2963152259WikidataQ129295416 ScholiaQ129295416MaRDI QIDQ1741847

Guus Regts, Viresh Patel

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilityinduced graphcomputational counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Algorithmic Pirogov-Sinai theory ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Weighted counting of solutions to sparse systems of equations

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Benjamini-Schramm continuity of root moments of graph polynomials
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Understanding the Complexity of Induced Subgraph Isomorphisms
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• The Parameterized Complexity of Counting Problems
• Left and right convergence of graphs with bounded degree
• Homomorphisms are a good basis for counting small subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item