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
Abstract:
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