SIA: Paul Wollan - Monday, May 31st, 2010, 12:00 noon

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

ABSTRACT:

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