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
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
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.