Colloquium by Sebastian Siebertz (Humboldt-Universität zu Berlin): First-order interpretations of sparse graph classes
The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal.
Time & Location
Nov 26, 2018 | 04:00 PM s.t.
Humboldt-Universität zu Berlin
Institut für Informatik
Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading])
Johann von Neumann-Haus
Rudower Chaussee 25