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.
• 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, MSO₂ model checking on bounded treewidth classes a.k.a Courcelle's theorem.
• Width measures for dense classes: clique-width, rankwidth, boolean-width. How they compare. MSO₁ model checking on bounded clique-width classes.
• Proper minor-closed classes, graphs on surfaces, Structure Theorem (general sketch).
• Twin-width, contraction sequences, classes with bounded twin-width, FO model checking on graphs given with a contraction sequence, Marcus-Tardos theorem, small classes.

And if time allows:

• Graph products, product structure theorem, some consequences.
• Tree-depth, polynomial-space algorithm on bounded tree-depth classes.
• Shallow minors, bounded expansion and nowhere dense classes, some characterizations, low tree-depth cover, p-centered colorings.
• FO model checking on classes with bounded expansion.

Lectures

Lecture 1, 05/09: Bird's eye view of the course.

Lecture 2, 06/09: Weighted Max Indepent Set (WMIS) on trees, path and tree decompositions, treewidth (tw), pathwidth, example of trees, cycles, grids, nice decompositions, WMIS in time 2^w n^O(1) when given a nice tree decomposition of width w. The lecture is covered by Chapter 7 up to 7.3.1 in the Parameterized Algorithms book.

Lecture 3, 12/09: Graph minors, statement of the Graph Minor Theorem, examples of minor-closed classes/properties, treedepth, statement of the Grid Minor Theorem, H-minor free graphs have bounded treewidth if and only if H is planar; see Chapter 6.3 in the Parameterized Algorithms book.

Lecture 4, 13/09: Bramble, bramble number (bn) of a graph, tw = bn-1, examples of cliques, cycles, grids. Grid Minor Theorem, the Planar Grid Minor Theorem, bidimensionality, subexponential parameterized algorithms for k-Vertex Cover and k-Path in planar graphs; see Section 7.7 up to 7.7.2 in the Parameterized Algorithms book. For the end of the proof of tw ≤ bn-1 left as an exercise, see this paper, last paragraph of Theorem 5, and page 2.

Lecture 5, 19/09: End of the sketch of the proof of Wagner's conjecture, FPT algorithm to compute tree-decompositions; see this chapter, and Chapter 7.6 in the Parameterized Algorithms book.

Lecture 6, 20/09: Color Coding for k-Path, Random Separation for Subgraph Isomorphism on bounded-degree hosts, contraction bidimensionality, Baker's technique, FO, MSO₁, example of sentences encoding k-Independent Set, k-Dominating Set, connectedness, 3-colorability; see Chapter 5.2 and 5.3, end of 7.7.2, 7.3, in the Parameterized Algorithms book.

Lecture 7, 29/09: MSO₂, example of Steiner Tree and Hamiltonian Cycle, definition of cliquewidth and rank-width, cliquewidth of cliques and trees, Courcelle's and Courcelle-Makowsky-Rotics's theorems (statement), Ehrenfeucht-Fraïssé games for FO, winning strategies on sets and on linear orders, Ehrenfeucht-Fraïssé theorem, quantifier rank, and rank-k types; see Chapter 7.4.2 and 7.9 in the Parameterized Algorithms book, and Chapter 3 in the Elements of Finite Model Theory book.

Lecture 8, 30/09: Linkage, continuation of FPT algorithm to compute tree-decompositions; see this chapter, and Chapter 7.6 in the Parameterized Algorithms book.

Lecture 9, 03/10: K_t,t-free graphs of bounded rank-width have bounded treewidth, linear orders, cographs, characterization with P₄-freeness, modular decompositions.

Lecture 10, 04/10: Connectedness is not FO-definable, Gaifman's theorem (statement) used for an FPT algorithm for FO model checking in bounded-degree graphs and planar graphs, MSO-EF games, MSO rank-k types, Spoiler's short winning strategy in connected/disconnected and planar/non-planar examples, MSO cannot express parity but MSO[<] can, Feferman-Vaught theorem, word/tree languages are regular if and only if MSO-definable (Büchi and Thatcher-Wright theorems), sketch of Courcelle's theorem; see end of Chapters 3 and 4, and Chapter 7 in the Elements of Finite Model Theory book.
(If you want to better understand how Gaifman's theorem is shown, you can read Chapter 4.)

Lecture 11, 10/10: Modular decompositions, twin-width, example of trees, grids, Bilu-Linial expanders, planar graphs (via the equivalence with grid number); see Sections 3 and 4 (and bits of 5 and 6) in this paper.

Lecture 12, 11/10: Interpretations, example of FO, MSO₁, MSO₂-interpretations, transductions, 1-subdivided cliques and interval graphs FO-transduces all graphs, grids MSO-transduces all graphs, component twin-width (ctww), ctww is tied to boolean-width/cliquewidth, how to use contraction sequences witnessing bounded ctww, example of 3-Coloring, Max Independent Set (details to sort out at home); see Sections 3.1 and 3.3 in this paper.

Lecture 13, 17/10: ; Families with unbounded twin-width (rook graphs and short subdivisions of cliques), 2 log n-subdivisions have twin-width at most 4, FPT algorithm for Max Independent Set with a d-sequence of component twin-width, general MSO₁ model checking algorithm (reproves Courcelle's theorems), MSO₁-transductions preserve bounded component twin-width, hence bounded cliquewidth; see Sections 3.2 in this paper.

Lecture 14, 18/10: Unit interval graphs have twin-width at most 2 (path of half-graphs), unit circular arc graphs have twin-width at most 3 (cycle of half-graphs), FPT algorithm for k-Dominating Set with a d-sequence, general FO model checking algorithm, chiboundedness, general graphs are not chi-bounded (Mycielskian), bounded twin-width are chi-bounded; see Sections 4 and 5 in this paper. You can also browse these slides.

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

The deadline for handing in the first homework is October 24.
The deadline for handing in the second homework is November 7.
You can, as you prefer, write or type your answers. In both cases, drawings are welcome.

The exam will on Tuesday 8th November (usual time, 8:00-10:00am).
On Monday 7th November, we will have a revision/exercise session.

References
Parameterized Algorithms by Cygan et al.
Graph Theory by Diestel.
Elements of Finite Model Theory by Libkin.
Sparsity by Ossona de Mendez and Nešetřil.