pith. sign in

arxiv: 1411.6226 · v1 · pith:BBPPG43Fnew · submitted 2014-11-23 · 🧮 math.CO

Disjoint paths in tournaments

classification 🧮 math.CO
keywords therealgorithmdigraphpathspolynomial-timesemicompletewhenbang-jensen
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.