A shorter proof for the disjoint paths algorithm

Series: 
Graph Theory Seminar
Friday, June 11, 2010 - 16:20
1 hour (actually 50 minutes)
Location: 
Skiles 254
,  
The Sapienza University of Rome
Organizer: 
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.