Skip to main content

Disjoint paths in tournaments

Author(s): Chudnovsky, Maria; Seymour, Paul D.; Scott, Alex

To refer to this page use:
Abstract: Given $k$ pairs of vertices $(s_i,t_i)$, $1\le i\le k$, of a digraph $G$, how can we test whether there exist $k$ vertex-disjoint directed paths from $s_i$ to $t_i$ for $1\le i\le k$? This is NP-complete in general digraphs, even for $k = 2$, but for $k=2$ there is a polynomial-time algorithm when $G$ is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen. Here we prove that for all fixed $k$ there is a polynomial-time algorithm to solve the problem when $G$ is semicomplete.
Publication Date: 22-Jan-2015
Electronic Publication Date: 1-Dec-2014
Citation: M. Chudnovsky, A. Scott, amd P. Seymour, Disjoint paths in tournaments, Adv Math 270 (2015), 582–597.
DOI: 10.1016/j.aim.2014.11.011
Pages: 582–597
Type of Material: Journal Article
Journal/Proceeding Title: Advances in mathematics.
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.