Structurally tractable graph classes

Michał Pilipczuk and Szymon Toruńczyk (University of Warsaw);

Course Summary | About the lecturers | Location and schedule Videos

Course summary:

An on-going 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 model-checking problem: does a given sentence of first-order 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 model-checking 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 twin-width, which seems to be an important piece of the puzzle. We will also see fixed-parameter tractability of the model-checking problem for various classes of bounded twin-width.

About the lecturer: Michał Pilipczuk is an assistant professor at the University of Warsaw. His research interests cover algorithms, complexity, and logic. He contributed to the development of fixed-parameter algorithms for a number of fundamental graph problems, for which parametrized algorithms have been sought-after since long time, and created new techniques like Cut-and-Count and Randomized Contractions. He also contributed to the bridge between algorithms and logic, in particular by solving (with Mikołaj Bojańczyk) a longstanding conjecture by Courcelle. He received the Cor Baayen award in 2016, and the ERC starting grant in 2020.

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 model-checking problem and structural properties of graphs.

Location and schedule:

ZOOM registration. The lectures will be recorded and posted below after each lecture.

Thursday, June 10 (Szymon Toruńczyk)
14:15 - 15:45 lecture
16:15 - 17:15 class
Friday, June 11 (Michał Pilipczuk, joint with FAS)
14:00 - 15:20 lecture
15:50 - 17:05 lecture
Saturday, June 12 (Szymon Toruńczyk)
10:15 - 11:45 lecture
12:15 - 13:15 class

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