Title: Disjoint paths in tournaments
Speaker: Paul Seymour, Princeton
Date: Thursday, January 25, 2011 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Given k pairs of vertices of a tournament, how can we test in polynomial time (for fixed k) whether there are k directed paths joining the pairs, pairwise vertex-disjoint? For k = 2, there was an algorithm by Bang-Jensen and Thomassen; but recently we found an algorithm for all fixed k.
It turns out the same algorithm also answers the following more general question -- given k pairs in a tournament, as before, and k integers, test whether the paths exist, pairwise vertex-disjoint, such that each path has length at most the corresponding integer.