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

Understand

We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a $k$-vertex graph $H$ in a $d$-degenerate $n$-vertex graph $G$.

• Our main result establishes exhaustive and explicit complexity classifications for counting subgraphs and induced subgraphs.
• We show that the (not necessarily induced) copies of $H$ in $G$ can be counted in time $f(k,d)\cdot n^{\max(\mathsf{imn}(H),1)}\cdot \log n$, where $f$ is some computable function and $\mathsf{imn}(H)$ is the size of the largest induced matching of $H$.
• Whenever the class of allowed patterns has unbounded induced matching number, this algorithm is essentially optimal: Unless the Exponential Time Hypothesis (ETH) fails, there is no algorithm running in time $f(k,d)\cdot n^{o(\mathsf{imn}(H)/\log \mathsf{imn}(H))}$ for any function $f$.