Structurally tractable graph classes
MichaÅ‚ Pilipczuk and Szymon ToruÅ„czyk
(University of Warsaw);
Course Summary 
About the lecturers 
Location and schedule
Videos
An ongoing program in structural graph theory and finite model theory aims to understand classes of finite structures
that can be considered simple from the point of view of the first order logic.
Here, simplicity can be understood both in terms of expressive power, and in terms of algorithmic tractability
of the corresponding modelchecking problem:
does a given sentence of firstorder logic hold in a given graph?
This program has been so far understood well in the context of sparse graphs, where the notion of nowhere denseness,
introduced by Nesetril and Ossona de Mendez, has been identified as the main dividing line.
Those classes include e.g. the class of all planar graphs or the class of all graphs with bounded
maximum degree. As it turns out, the modelchecking problem can be solved in time
almost linear with respect to the graph size, when the graph comes from a fixed nowhere dense class.
We will see some special cases of this result, e.g. for the class of planar graphs or classes with bounded maximum degree.
The corresponding dividing line for classes of dense graphs is yet to be understood. Very recently, Bonnet, Kim, ThomassÃ©, and Watrigant introduced
a new parameter called twinwidth, which seems to be an important piece of the puzzle.
We will also see fixedparameter tractability of the modelchecking problem for various classes
of bounded twinwidth.
Szymon ToruÅ„czyk is an assistant professor at the University of Warsaw, where he received a habilitation degree in 2020. He works on mathematical problems in computer science in a variety of areas including automata, logic, and databases. He has published at topmost venues like PODS, POPL, LICS, and received best paper award at PODS 2013 and FoSSaCS 2021, as well as the Ackermann award in 2012. His recent work reveals deep connections between complexity of the modelchecking problem and structural properties of graphs. Location and schedule:
ZOOM registration. The lectures will be recorded and posted below after each lecture.



Videos: The video recordings of the lectures are now available.
Assignment: assignment. Please submit the solutions by 15 September (CET).