Homomorphisms Are a Good Basis for Counting Small Subgraphs

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ász 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 $\mathcal{C}$ of such parameters, we consider the problem of evaluating $f\in \mathcal{C}$ on input graphs $G$, parameterized by the number of induced subgraphs that $f$ depends upon. For every recursively enumerable class $\mathcal{C}$, 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 $\mathcal{H}$, 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.

An extended abstract of this paper appears at STOC 2017

References in corpus (4)

• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• The Parameterized Complexity of k-Biclique
• Lower bounds for approximation schemes for Closest String
• The parameterised complexity of counting even and odd induced subgraphs

Cited by in corpus (11)

• Graph Neural Networks with Local Graph Parameters
• Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
• Four short stories on surprising algorithmic uses of treewidth
• Two dichotomies for model-checking in multi-layer structures
• Signatures of graphs for bicommutative Hopf algebras
• Homomorphism Tensors and Linear Equations
• Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
• Parameterized Valiant's Classes
• Number of Connected Components in a Graph: Estimation via Counting Patterns
• Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity