Algorithmic Meta-Theorems (2021)

Instructor: Jan Dreier

In the first block, we define treewidth (part 2), and show that all problems definable in monadic second-order logic can be solved efficiently on graph classes with bounded treewidth (part 3 and 4).
In the second block, we show that all problems definable in first-order logic can be solved efficiently on more and more general sparse graphs. After proving the result for graph classes with bounded degree and bounded local treewidth (part 5), we introduce the notions of bounded expansion and nowhere dense graph classes (part 6) and solve all problems definable in first-order logic on bounded expansion graph classes (part 7 and 8). We close with a short overview over dense graph classes (part 9).

Slides

Part 1: Introduction
Part 2: Treewidth
Part 3: Courcelle's Theorem I
Part 4: Courcelle's Theorem II
Part 5: Gaifman Locality
Part 6: Sparsity Definitions
Part 7: Model-Checking
Part 8 and 9: Dense Graphs

Recordings