Monday, October 31, 2011
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041
Lecture - 14:15
Many natural computational problems on graphs, such as finding dominating or independent sets of a certain size, are well known to be intractable, both in the classical sense as well as in the framework of parameterized complexity. Much work therefore has focussed on exhibiting specific classes of graphs on which these problems become tractable.
One aspect of this research is to identify classes of graphs which are
1) as general as possible so that graphs of this form can be used in a wide range of applications but
2) restricted enough so that typical algorithmic problems become tractable.
For this, methods derived from the structure theory for undirected graphs has proved to be very successful. For instance, it has been shown that a many hard problems are tractable on graph classes of bounded tree-width or which exclude a fixed minor.
Towards a Structure Theory for Directed Graphs based on Minors While in the case of undirected graphs, there is a rich structure theory which can be used to establish tractability results for these problems on large classes of undirected graphs, such a theory is much less developed for directed graphs. However, as directed graphs occur naturally in many applications in computer science, developing such a structure theory for directed graphs seems to be an important goal.
In this talk we will review some of the structural methods used to solve hard computational methods on specific classes of undirected graphs, in particular methods based on excluding minors or new approaches based on nowhere denseness.
In the second part of the talk, we will focus on very recent ideas to generalise the minor theory to directed graphs for obtaining tractability results on large classes of digraphs.
Instead of Colloquium - 16:00