Édouard Bonnet - Home Page

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

Lecture 1, 07/09: Weighted Max Indepent Set (WMIS) on trees, path and tree decompositions, treewidth, pathwidth, example of trees, cycles, cliques, 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 2, 09/09: About computing the treewidth, equivalence of pathwidth via search number and interval thickness/width, pathwidth of trees, equivalence of treewidth via cop number, chordal thickness/width, and bramble number, treewidth lowerbound for cycles, cliques, grids with brambles. The lecture is covered by Sections 7.5 and 7.6 in the Parameterized Algorithms book.

Lecture 3, 14/09: Minor of a graph, first connection with treewidth and brambles, grid minor theorem, its planar (contraction) version, algorithmic application of bidimensionality (small treewidth or large grid minor), example of k-Vertex Cover, k-Path, k-Dominating Set, in general graphs: branching for k-Vertex Cover and Color Coding for k-Path. See Sections 7.7.1 and 7.7.2 in the Parameterized Algorithms book (as well as Sections 3.1 and 5.2).

Lecture 4, 16/09: Examples of minor-closed classes: forests, outerplanar, planar, toroidal graphs, treewidth at most k, their clique and chromatic numbers, Wagner's and Hadwiger's conjectures, excluding as a minor a 4-vertex clique, a path, a planar graph, start of the outline of the resolution of Wagner's conjecture. See Section 6.3 in the Parameterized Algorithms book.

Lecture 5, 21/09: Baker's technique. Basic definitions in finite model theory, signatures, models, first-order formulas/sentences, model checking, inexpressibility using the compactness theorem, its limits for finite models, Ehrenfeucht-Fraïssé games, examples on sets, on linear orders, rank-k types, defining formula of a type, "EF general strategy" to show that a query is not FO-definable. See Section 7.7.3 in the Parameterized Algorithms book, and Section 2.1 and Sections 3.1 to 3.4 in Libkin's book.

Lecture 6, 23/09: Higman's lemma, Kruskal's tree theorem, the minor relation is a wqo for trees, bounded treewidth graphs, planar graphs (via the Grid Minor theorem), Structure Theorem to lift it to any graph class excluding a fixed minor, hence the Robertson-Seymour theorem. See Chapter 12 in Diestel's book Graph Theory.

Lecture 7, 28/09: End of Graph Minor theorem, computing treewidth in FPT time.

Lecture 8, 30/09: Cographs, clique-width, branch-decompositions.

Lecture 9, 05/10: Ehrenfeucht-Fraïssé theorem, completeness of the approach ruling out FO definability, example of connectedness, planarity, hamiltonicity, inexpressibility by interpretation (reduction), Hanf locality, Gaifman locality, similar strategy to rule out FO definability. End of Chapter 3 and start of Chapter 4 in Libkin's book.

Lecture 10, 07/10: Branchwidth, rankwidth, tangles.

Lecture 11, 12/10: Hanf-locality implies Gaifman-locality, every FO definable query is Hanf-local, examples of planarity, transitive closure, balanced ternary tree, same level in a tree, Gaifman's locality theorem, application to FPT FO model checking in bounded-degree graphs, SO and MSO, planarity is MSO definable, exercises at home: connectedness, cyclicity, and k-colorability are MSO definable, Courcelle's theorems (statement). End of Chapter 4 and start of Chapter 6 in Libkin's book.

Lecture 12, 14/10: Vertex-minors, introduction to twin-width, the Guillemot-Marx algorithm and the Marcus-Tardos theorem.

Lecture 13, 19/10: Twin-width of cographs, paths, trees, grids, component twin-width.

Lecture 14, 21/10: Component twin-width and rank-width/boolean-width are functionally equivalent, Maximum Independent Set on cographs with the contraction sequence viewpoint, first example of dynamic programming on a contraction sequence (with errors): q-Coloring on graphs given with a component twin-width sequence, generalization to MSO model checking (alternative proof of Courcelle's theorem).

Lecture 15, 26/10: Characterization of bounded twin-width by mixed minors and bounded oriented twin-width, example of use: Kt-minor free classes and posets of dimension 2 have bounded twin-width, small classes, classes of bounded twin-width are small, FO interpretations, every interpretation of a bounded twin-width class has bounded twin-width (statement), example of use: 1-planar graphs have bounded twin-width.

Lecture 16, 28/10: FPT algorithm running in time 2^{O(k log d)} n for k-Independent Set on n-vertex graphs given with a d-sequence, generalization to the entire FO model checking, FO transductions, every transduction of a bounded twin-width class has bounded twin-width, example of use from planar graphs: bounded-degree segment graphs have bounded twin-width.

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.