A shorter proof for the disjoint paths algorithm

Series
Graph Theory Seminar
Time
Friday, June 11, 2010 - 4:20pm for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Paul Wollan – The Sapienza University of Rome
Organizer
Robin Thomas
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 23 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, eliminating many of the technicalities of the original proof. This is joint work with Ken-ichi Kawarabayashi.