Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

We consider the problem of counting the copies of a k-node graph H in an n-node graph G. Due to the sparsity of real-world graphs, there is considerable interest in understanding the complexity of this problem when the degeneracy d of G is small. In this work we present several results on this topic. Our main contributions are:

• We fully classify the complexity of counting the copies and the induced copies of H in ddegenerate graphs G, under the Exponential Time Hypothesis. We prove that the copies of H in G can be counted in time f (k, d)•n max(imn(H),1) •log n, where imn(H) is the size of the largest induced matching of H, and that this is essentially optimal: if the class of allowed patterns has unbounded induced matching number, the problem cannot be solved in time f (k, d)•n o(imn(H)/ log imn(H)) for any f . We show a similar result for counting induced copies, in which case the relevant parameter of H turns out to be its independence number α(H).

In the language of parameterized complexity, this gives dichotomies in tractable and hard cases when the parameter is k + d, and implies that, unless ETH fails, several patterns cannot be counted in time f (k, d) • n o(k/ log k) , including k-matchings, k-independent sets, (induced) k-paths, (induced) k-cycles, and induced (k, k)-bicliques.

• We introduce a novel family of obstructions, that we call F-gadgets, which are at the heart of our hardness results. We show that counting the homomorphisms from H to a graph of bounded degeneracy is hard when H has an F -gadget of unbounded treewidth. From this result, the hardness results for subgraphs and induced subgraphs above are derived using the complexity monotonicity principle of Curticapean, Dell and Marx (STOC 17) and Chen and Mengel (PODS 16), via a recent approach of Gishboliner, Levanzov and Shapira (ECCC 20). We conjecture that F-gadgets actually characterise the hardness of counting homomorphisms in graphs of bounded degeneracy. Our work proves one part of this conjecture, leaving the other part as an open problem.

• We give novel algorithms for approximate counting of subgraphs and induced subgraphs, based on recent reductions to the colourful decision version of the problem by Dell, Lapinskas and Meeks (SODA 20). We show an algorithm that computes an expected εmultiplicative approximation of the number of copies of 1) , where τ 1 (H) is the dag-treewidth of H. For induced copies, we give an algorithm with running time (kd 1) . This implies, for instance, that we can efficiently approximate the number of induced (k, k)-bicliques in a degenerate graph, which for non-degenerate graphs is impossible under standard parameterized complexity assumptions.

Open Problem. Let k be a positive integer and let G be an n-vertex graph of degeneracy d.

Note that we chose the problem of counting induced k-matchings in degenerate graphs, since exact counting is hard by Theorem 5, but its decision version is known to be fixed-parameter tractable [32]. Furthermore, k-matchings constitute the minimal class of graphs for which our algorithm for approximating induced subgraph counts (see Theorem 13) does not yield fixedparameter tractability.