| Title | : | A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs |
| Speaker | : | Daniel Paul-Pena (University of California, Santa Cruz) |
| Details | : | Tue, 9 Dec, 2025 3:00 PM @ SSB 334 |
| Abstract: | : | Subgraph and homomorphism counting are fundamental algorithmic problems. 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 Nesetril 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. This is a joint work with C. Seshadhri. |
