A Dichotomy Hierarchy Characterizing Linear Time Subgraph Counting in Bounded Degeneracy Graphs

Daniel Paul-Pena, C. Seshadhri

Subgraph and homomorphism counting are fundamental algorithmic problems. Given a constant-sized pattern graph $H$ and a large input graph $G$, we wish to count the number of $H$-ho…