Bera, Pashanasangi, and Seshadhri recently raised the question of characterizing the graphs $H$ such that counting $H$-copies in a bounded-degeneracy input graph can be done in linear time. In this work we fully resolve this question, as well as the analogous questions for counting $H$-homomorphisms and induced $H$-copies. A recent result of Bressan shows that one can count $H$-homomorphisms in a bounded-degeneracy graph in time $O(n^{\tau(H)})$, where $\tau$ is a suitable width parameter, called DAG treewidth. In particular, $H$-homomorphisms can be counted in linear time if $\tau(H) = 1$. We show that this sufficient condition is also necessary, namely that $H$-homomorphisms can be counted in linear time if and only if $\tau(H) = 1$. We then use this to resolve the aforementioned problem of Bera, Pashanasangi, and Seshadhri. Our proofs rely on several new ideas for proving hardness results in the context of subgraph-counting.
This is a joint work with Yevgeny Levanzov and Asaf Shapira.