Faster subgraph counting in sparse graphs

A fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [28], with running time f(k) · O(nωb k3 c+2) where ω ≤ 2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth τ(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d, k) · Õ(nτ(H)); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d, k) · no(τ(H)/ ln τ(H)) for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on τ(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d = O(poly log(n)) we can count the induced copies of any H in time f(k) · Õ(nb k4 c+2), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n.