Monday, May 2, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
It was realized already in the early days of the algorithm design that many problems that are intractable in general, become efficiently solvable on planar graphs. In the paradigm of parameterized complexity, the fundamental technique for designing fast algorithms on planar graphs is bidimensionality: exploiting the linear relation between "tree-likeness" of a planar graph and the maximum size of a bidimensional object that can be embedded into it. Even though bidimensionality provides close to optimal algorithms for a number of fundamental parameterized problems on planar graphs, there are numerous cases where the technique fails to be applicable, and where we are unable to use the planarity assumption in any meaningful way. During the talk we will introduce the method of bidimensionality, discuss its strengths and weaknesses, and present the most recent advances on extending it to more general classes of problems.
Colloquium - 16:00
Abstract:
Bounded expansion and nowhere dense classes of graphs were
introduced by Nesetril and Ossona de Mendez as formalisations of
uniformly sparse graphs. Grohe, Kreutzer and Siebertz presented
a very intuitive characterisation of nowhere dense classes in terms
of a game, called the splitter game. A similar game characterisation
can be given for classes of bounded expansion. In this talk, we
are going to compare the two games and derive new bounds for
parameters that characterise bounded expansion and nowhere dense
classes of graphs. We are going to present our recent result that
classes with excluded topological minors admit uniform winning
strategies in the game and sketch a proof that such classes admit
efficient model-checking for successor-invariant first-order formulas.