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

Abstract

Subgraph and homomorphism counting are fundamental algorithmic problems. Given a constant-size 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 studying when (near) linear-time algorithms are possible. The seminal work of Chiba-Nishizeki (SICOMP 1985) shows that for bounded-degeneracy input classes, clique and 4-cycle counting can be done in 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. At the other end, Nešetřil and Ossona de Mendez used their deep theory of “sparsity” to define graph classes with bounded expansion (which contains all non-trivial minor-closed families). 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 answer the above questions. We show the existence of an infinite sequence of families of graph classes \(\mathcal {G}_0 \supseteq \mathcal {G}_1 \supseteq \ldots \supseteq \mathcal {G}_\infty \) where \(\mathcal {G}_0 \) is the family of bounded-degeneracy classes, and \(\mathcal {G}_\infty \) is the family of bounded expansion classes. Fix any constant-size 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 ) ≥ 3( r + 2), then (assuming fine-grained complexity conjectures) H -homomorphism counting on inputs from \(\mathcal {G}_r \) takes Ω ( n 1 + γ ) time. (Here, n denotes the number of vertices of the input, and γ is some explicit constant.) Similar dichotomy theorems hold for subgraph counting.