Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
Marco Bressan, Marc Roth · 2022
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.