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)n^{\max(1,\mathsf{imn}(H))} \log n$
, where
$f$
is some computable function and
$\mathsf{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)/\log \mathsf{imn}(H))}$
for any function
$f$
, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number
$\alpha(H)$
in place of
$\mathsf{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.