Homomorphisms Are a Good Basis for Counting Small Subgraphs

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 kO(k)· n0.174k + o(k) by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k + c) time for k-edge matchings or O(n0.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∈ 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.