Homomorphisms are a good basis for counting small subgraphs

DOI10.1145/3055399.3055502zbMATH Open1369.05191arXiv1705.01595OpenAlexW2610844084MaRDI QIDQ4977973FDOQ4977973

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)

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.

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

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

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)

Cited In (44)

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

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)