Abstract:
Algorithmic meta theorems give efficient algorithms for classes of algorithmic problems, instead of just individual problems. They unify families of algorithmic results obtained by similar techniques and thus exhibit the core of these techniques. The classes of problems are typically defined in terms of logic and structural graph theory. A well-known example of an algorithmic meta theorem is Courcelle's Theorem, stating that all properties of graphs of bounded tree-width that are definable in monadic second-order logic are decidable in linear time.

In this talk, I will focus on algorithmic meta theorems for sparse graph classes, inlcuding classes of bounded tree width, the class of planar graphs and all graph classes with excluded minors, classes of bounded expansion and most generally classes of nowhere dense graphs.