Bounded treedepth, bounded expansion, and their interpretations

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski

Date

Jan. 17, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---