Homomorphisms are a good basis for counting small subgraphs

DOI10.1145/3055399.3055502MaRDI QIDQ4977973zbMATHOpenAlexFDO

Authors Radu Curticapean, Holger Dell, 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

fixed-parameter tractabilitycounting subgraphshomomorphismsexponential-time hypothesis

Mathematics Subject Classification ID

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

Abstract: We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lov'asz show that many interesting quantities have this form, including, for fixed graphs $H$, the number of $H$-copies (induced or not) in an input graph $G$, and the number of homomorphisms from $H$ to $G$. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs $H$ in host graphs $G$: For graphs $H$ on $k$ edges, we show how to count subgraph copies of $H$ in time $k^{O(k)}cdot{n}^{0.174k+o(k)}$ by a surprisingly simple algorithm. This improves upon previously known running times, such as $O(n^{0.91k+c})$ time for $k$-edge matchings or $O(n^{0.46k+c})$ time for $k$-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class $mathcalC$ of such parameters, we consider the problem of evaluating $finmathcalC$ on input graphs $G$, parameterized by the number of induced subgraphs that $f$ depends upon. For every recursively enumerable class $mathcalC$, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs $H$ and $G$, where $H$ is from a fixed class $mathcalH$, we want to count color-preserving $H$-copies in $G$. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions.

Recommendations

• Counting Subgraphs via Homomorphisms
• Counting subgraphs via homomorphisms
• Faster algorithms for counting subgraphs in sparse graphs
• Counting and detecting small subgraphs via equations
• Faster algorithms for finding and counting subgraphs

Cited in

(45)

• Local WL invariance and hidden shades of regularity
• Finding and counting small tournaments in large tournaments
• On the problem of finding small subdivision and homomorphism bases for classes of countable graphs
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Algebraic global gadgetry for surjective constraint satisfaction
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Compactors for parameterized counting problems
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• Parameterized counting of partially injective homomorphisms
• Parameterized (Modular) Counting and Cayley Graph Expanders
• Counting Subgraphs in Degenerate Graphs
• Faster algorithms for counting subgraphs in sparse graphs
• Counting Answers to Existential Questions
• Parameterised counting in logspace
• The complexity of counting surjective homomorphisms and compactions
• Counting subgraphs via homomorphisms
• Counting connected subgraphs with maximum-degree-aware sieving
• Tensor network complexity of multilinear maps
• Counting Subgraphs via Homomorphisms
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Parameterized Counting and Cayley Graph Expanders
• scientific article; zbMATH DE number 7561323 (Why is no real title available?)
• A fixed-parameter perspective on \#BIS
• Counting problems in parameterized complexity
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Counting Homomorphic Cycles in Degenerate Graphs
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• Monotone arithmetic complexity of graph homomorphism polynomials
• A fixed-parameter perspective on \#BIS
• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Counting Small Induced Subgraphs with Hereditary Properties
• Parameterised and fine-grained subgraph counting, modulo 2
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Counting subgraphs in somewhere dense graphs
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Faster Subgraph Counting in Sparse Graphs
• Quasipolynomiality of the Smallest Missing Induced Subgraph

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

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