A Dichotomy Hierarchy for 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 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 G. At the other end, Nešetřil and Ossona de Mendez used their deep theory of “sparsity” to define bounded expansion graphs (which contains all 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?