Dr. Sebastian Siebertz, Berlin
“Limits of algorithmic tractability”
Many structural properties of graphs can be exploited in the design of efficient algorithms for otherwise hard problems. The celebrated structure theory of graphs with excluded minors, developed by Robertson and Seymour, had an immense influence on the design of efficient algorithms. In particular the concept of tree-width, which they introduced as part of their graph minors project, proved extremely valuable in the algorithmic context. A complete shift in paradigm was initiated by Nešetril and Ossona de Mendez with their ground-breaking work on bounded expansion and nowhere dense classes of graphs. Many familiar classes of sparse graphs, like planar graphs, graphs of bounded treewidth, graphs of bounded degree, and, in fact, all classes that exclude a fixed (topological) minor, are nowhere dense. This rich theory has been successfully applied to design efficient algorithms for hard computational problems on specific sparse classes of graphs. On the other hand, several results indicate that nowhere dense graph classes form a natural limit for algorithmic methods based on sparseness arguments.
In my talk I will give an introduction to the theory of nowhere dense graphs with a focus on algorithmic applications. I will then present some of my recent results that combine methods for sparse graphs with stability theory, which is one of the most successful areas of contemporary logic. I will conclude with an outlook on the systematic study of the logical structure of graphs underlying algorithmic tractability.
12.01.2018 | 16:15 - 17:45
Takustr. 9, SR 049