Homomorphisms are a good basis for counting small subgraphs

DOI10.1145/3055399.3055502zbMath1369.05191arXiv1705.01595OpenAlexW2610844084MaRDI QIDQ4977973

Holger Dell, Radu Curticapean, Dániel Marx

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

homomorphismsfixed-parameter tractabilitycounting subgraphsexponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (34)

Compactors for parameterized counting problems ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Parameterised counting in logspace ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local WL invariance and hidden shades of regularity ⋮ Computing the number of induced copies of a fixed graph in a bounded degree graph ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Unnamed Item ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Counting Answers to Existential Questions ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

This page was built for publication: Homomorphisms are a good basis for counting small subgraphs