Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Vertex-disjoint paths in tournaments
Speaker: Maria Chudnovsky, Columbia University
Date: Thursday, November 18, 2010 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The question of linking pairs of terminals by disjoint paths is a standard and well-studied question in graph theory. The setup is: given vertices s1,..,sk and t1,..,tk, is there a set of disjoint path P1,..,Pk such that Pi is a path from si to ti? This question makes sense in both directed and undirected graphs, and the paths may be required to be edge- or vertex-disjoint.
For undirected graphs, a polynomial-time algorithm for solving both the edge-disjoint and the vertex-disjoint version of the problem (where the number k of terminals is fixed) was first found by Robertson and Seymour, and is a part of their well-known Graph Minors project. For directed graphs, both problems are NP-complete, even when k=2 (by a result of Fortune, Hopcroft and Wyllie). However, if we restrict our attention to tournaments (these are directed graphs with exactly one arc between every two vertices), the situation improves. Polynomial time algorithms for solving the edge-disjoint and the vertex-disjoint paths problems when k=2 have been known for a while (these are results of Bang-Jensen, and Bang-Jensen and Thomassen, respectively).
Last year, Fradkin and Seymour were able to design a polynomial-time algorithm to solve the edge-disjoint paths problem in tournaments for general (fixed) k, using a new parameter for tournaments, developed by Seymour and the speaker, called "cut-width". However, the vertex-disjoint paths problem seemed to be resistant to similar methods. This talk will focus on the polynomial- time algorithm to solve the vertex-disjoint paths problem in tournaments for general (fixed) k, that we have recently obtained in joint work with Scott and Seymour.