| Title | : | A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs |
| Speaker | : | Daniel Paul-Pena (University of California, Santa Cruz) |
| Details | : | Tue, Dec 9, 2025 3:00 PM, @ SSB 334 |
| Abstract | : | 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. Bio: Daniel Paul-Pena is a 5th year PhD Candidate at the University of California, Santa Cruz, under the supervision of Prof. C. Seshadhri. His main research interest is in subgraph counting, with special emphasis in finding algorithms that translate well into practice. |