Homomorphisms are a good basis for counting small subgraphs

DOI10.1145/3055399.3055502MaRDI QIDQ4977973zbMATH OpenOpenAlexFDO

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, http://eprints.sztaki.hu/9230/

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)

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

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)