Seminars
View all Seminars | Download ICal for this eventA Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs
Series: Bangalore Theory Seminars
Speaker: Daniel Paul Pena, University of California, Santa Cruz
Date/Time: Dec 15 11:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
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 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. This work was presented at SODA 2025.
Microsoft Teams link:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: Rameesh Paul, Nirjhar Das, KVN Sreenivas, Debajyoti Kar, Rahul Madhavan