When: Monday, May 31st, 2010, 12:00 noon
Where: DIS - Dipartimento di Informatica e Sistemistica, Via Ariosto 25
Speaker: Paul Wollan, Dipartimento di Informatica, "Sapienza" Università di Roma
Title: A shorter proof for the disjoint paths algorithm
The theory of graph minors developed by Robertson and Seymour is perhaps one of the deepest developments in graph theory. The theory is developed in a sequence of 24 papers, appearing from the 80's through today. The major algorithmic application of the work is a polynomial time algorithm for the k disjoint paths problem when k is fixed. The algorithm is relatively simple to state - however the proof uses the full power of the Robertson Seymour theory, and consequently runs approximately 400-500 pages. We will discuss a new proof of correctness that dramatically simplifies this result, making it accessible to people with only a general knowledge of graph theory. In this talk, we will not assume any previous acquaintance with graph minors.
This is joint work with Ken-ichi Kawarabayashi