A shorter proof for the disjoint paths algorithm

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