- Series
- Graph Theory Seminar
- Time
- Monday, February 28, 2011 - 2:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 168
- Speaker
- Paul Wollan – School of Mathematics, Georgia Tech and University of Rome
- Organizer
- Robin Thomas
The k-disjoint paths problem takes as input a graph G and k pairs of
vertices (s_1, t_1),..., (s_k, t_k) and determines if there exist
internally disjoint paths P_1,..., P_k such that the endpoints of P_i
are s_i and t_i for all i=1,2,...,k. While the problem is NP-complete
when k is allowed to be part of the input, Robertson and Seymour showed
that there exists a polynomial time algorithm for fixed values of k. The
existence of such an algorithm is the major algorithmic result of the
Graph Minors series. The original proof of Robertson and Seymour relies
on the whole theory of graph minors, and consequently is both quite
technical and involved. Recent results have dramatically simplified the
proof to the point where it is now feasible to present the proof in its
entirety. This seminar series will do just that, with the level of
detail aimed at a graduate student level.