A Dichotomy Hierarchy Characterizing Linear Time Subgraph Counting in Bounded Degeneracy Graphs
Daniel Paul Pena (UCSC)
Monday, November 25th 2024, 2-3pm
Abstract:
Subgraph and homomorphism counting are fundamental algorithmic problems. Can we characterize which patterns can be counted in linear time? Recent work (Bera et al. SODA 2021, JACM 2022) provided a characterization of the patterns that can be counted in linear time for bounded degeneracy inputs. An older result by Nešetřil and Ossona de Mendez proved that for input graphs in classes with bounded expansion all the patterns can be counted in linear time. What lies between?
We present a hierarchy of dichotomies that closes the gap between both results, completely and precisely characterizing the instances that are linear time computable. The result uses ideas from graph sparsity, generalized notions of tree decompositions, and techniques from subgraph counting in sparse graphs.
Based on joint work with C. Seshadhri