February 5, 2007
Humboldt Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Lecture: Raum 0'313 im Erwin-Schrödinger Zentrum (Rudower Chaussee 26)
Colloquium: Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
Graph minor theory, mainly developed by Robertson and Seymour in a long series
of papers, is a structure theory for graphs with excluded minors. It
culminates in the graph minor theorem, which states that every class of
graphs closed under taking minors can be characterised by a finite set of
excluded minors.
But the theory also has significant algorithmic consequences. Most notably,
Robertson and Seymour used it to prove that for every fixed k, the k-disjoint
paths problem has a cubic time algorithm. This answered a long standing open
problem in an unexpected way. More recently, results from graph minor theory
have been combined with algorithmic techniques that had originally been
developed for planar graphs to obtain polynomial time approximation schemes
and fixed parameter tractable algorithms for many standard optimisation
problems on families of graphs with excluded minors.
In this talk, I will give brief introduction into the main structural results
of graph minor theory and then explain both Robertson and Seymour's fundamental
algorithms and the more recent advances in the field.
Colloquium - 16:00
Abstract:
The notion of brambles gives a dual characterization of tree width:
Seymour and Thomas proved that a graph has a tree decomposition of width
k if and only if every bramble has order at most k+1. In this talk we
investigate this notion and examine what happens if we would like to
have brambles of polynomial size. We are able to show that every graph
has a polynomial-size bramble whose order is roughly the square root of
the tree width of the graph, but there are graphs where every bramble
with order larger than the square root of the tree width has to be of
exponential size.