Bounded treedepth, bounded expansion, and their interpretations

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

17 stycznia 2018 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

Classes of bounded expansion are quite general classes of sparse graphs,
for which many algorithmic problems which are hard in general become 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 algorithmic results
to classes of graphs which are not sparse, we study first order interpretations
of classes of bounded expansion. As a first step towards their algorithmic treatment,
we provide a characterization of such graph classes in terms of graph classes of
bounded shrubdepth, which are first-order interpretations of classes of trees of bounded depth.

---