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

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$-homomorphisms/subgraphs in $G$. Given the massive sizes of real-world graphs and the practical importance of counting problems, we focus on when (near) linear time algorithms are possible. The seminal work of Chiba-Nishizeki (SICOMP 1985) shows that for bounded degeneracy graphs $G$, clique and $4$-cycle counting can be done linear time. Recent works (Bera et al, SODA 2021, JACM 2022) show a dichotomy theorem characterizing the patterns $H$ for which $H$-homomorphism counting is possible in linear time, for bounded degeneracy inputs $G$. At the other end, Nešetřil and Ossona de Mendez used their deep theory of “sparsity” to define bounded expansion graphs. They prove that, for all $H$, $H$-homomorphism counting can be done in linear time for bounded expansion inputs. What lies between? For a specific $H$, can we characterize input classes where $H$-homomorphism counting is possible in linear time? We discover a hierarchy of dichotomy theorems that precisely answer the above questions. We show the existence of an infinite sequence of graph classes ${\mathcal{G}}_0$ $\supseteq$ ${\mathcal{G}}_1$ $\supseteq$ … $\supseteq$ ${\mathcal{G}}_{\mathrm{\infty }}$ where ${\mathcal{G}}_0$ is the class of bounded degeneracy graphs, and ${\mathcal{G}}_{\mathrm{\infty }}$ is the class of bounded expansion graphs. Fix any constant sized pattern graph $H$. Let $LICL(H)$ denote the length of the longest induced cycle in $H$. We prove the following. If $LICL(H)<3(r+2)$, then $H$-homomorphisms can be counted in linear time for inputs in ${\mathcal{G}}_r$. If $LICL(H)\ge 3(r+2)$, then $H$-homomorphism counting on inputs from ${\mathcal{G}}_r$ takes $\mathrm{\Omega }(m^{1+\gamma })$ time. We prove similar dichotomy theorems for subgraph counting.