**Graph Decompositions**

Lecturers: Édouard Bonnet and Stéphan Thomassé

We take a journey through forty years of decompositions of finite structures and some of their algorithmic and combinatorial consequences.
The several milestones that we will cover comprise the inception of treewidth in the 80's, and the subsequent Graph Minors project, algorithmic meta-theorems based on width decompositions in the 90's, the sparsity program instigated in the first decade of the millennium, and finally fresh additions to the topic in the so-called product structure theorem and twin-width, both happening within the last three years.
Algorithmically we put the focus on meta-theorems and fixed-parameter tractable model checking.

The course intends to provide the fundamental background to access, sketch, and sometimes prove classic results in (algorithmic) graph theory, as well as recent developments therein.
As a by-product of the course, the student will get familiar with the basics of finite model theory, graph model checking, and parameterized algorithms.

**Tentative Outline**

- Treewidth, graph minors, grid minor theorem, and some of their algorithmic applications: minor-closed problems, dynamic programming over tree-decompositions, bidimensionality, irrelevant vertex. (3 x 2h)
- First-Order (FO) and Monadic Second-Order (MSO) logics, basics of finite model theory, Feferman-Vaught theorem, Gaifman's theorem, FO model checking on locally simple classes, MSO2 model checking on bounded treewidth classes a.k.a Courcelle's theorem. (2 x 2h)
- Width measures for dense classes: clique-width, rankwidth, boolean-width. How they compare. MSO1 model checking on bounded clique-width classes. (2 x 2h)
- Proper minor-closed classes, graphs on surfaces, Structure Theorem (general sketch). (1 x 2h)
- Graph products, product structure theorem, some consequences. (2 x 2h)
- Tree-depth, polynomial-space algorithm on bounded tree-depth classes. (1 x 2h)
- Shallow minors, bounded expansion and nowhere dense classes, some characterizations, low tree-depth cover, p-centered colorings. (2 x 2h)
- FO model checking on classes with bounded expansion. (1 x 2h)
- Twin-width, contraction sequences, classes with bounded twin-width, FO model checking on graphs given with a contraction sequence. (2 x 2h)

**Lectures**

*Parameterized Algorithms*book.

*Parameterized Algorithms*book.

*Parameterized Algorithms*book (as well as Sections 3.1 and 5.2).

*Parameterized Algorithms*book.

*Parameterized Algorithms*book, and Section 2.1 and Sections 3.1 to 3.4 in Libkin's book.

*Graph Theory*.

You can find the content of the last five lectures (and more) in the following four papers.

The exam will take place on Tuesday 9th November at the usual time (1:30-3:30pm) and in the usual room (B1). Lecture notes are allowed.

**Evaluation**

Homework 1 (25%) + Homework 2 (25%) + Exam (50%)

**References**

Elements of Finite Model Theory by Libkin.

~~Sparsity by Ossona de Mendez and Nešetřil.~~
Parameterized Algorithms by Cygan et al.