Disjoint paths in unions of tournaments
classification
🧮 math.CO
keywords
digraphtherealgorithmfixedgivenpathspolynomial-timeproblem
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 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 in an earlier paper we proved that for all fixed $k$, there is a polynomial-time algorithm to solve the problem if $G$ is a tournament (or more generally, a semicomplete digraph). Here we prove that for all fixed $k$ there is a polynomial-time algorithm to solve the problem when $V(G)$ is partitioned into a bounded number of sets each inducing a semicomplete digraph (and we are given the partition).
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.