Faster algorithms for counting subgraphs in sparse graphs.

Given a -node pattern graph and an -node host graph , the subgraph counting problem asks to compute the number of copies of in . In this work we address the following question: can we count the copies of faster if is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of in by exploiting the degeneracy of , which allows us to beat the state-of-the-art subgraph counting algorithms when is sparse enough. For example, we can count the induced copies of any -node pattern in time if has bounded degeneracy, and in time if has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of and the structure of , which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.