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