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

We study the problems of counting the homomorphisms, the copies, and the induced copies of a k-vertex graph H in a d-degenerate n-vertex graph G. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance., we show that the copies of H in G can be counted in time f(k, d)nmax(1,mathsf{imn(H)} log n, where f is some computable function and imn (H) is the size of the largest induced matching of H; and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time f(k, d)n o(mathsf{imn(H)/logmathsf{imn(H) for any function f, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number α(H) in place of imn(H). These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when d is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as k-matchings and k-trees, in d-degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i.e., counting patterns with a given property) in degenerate graphs.