JOURNAL OF COMBINATORIAL THEORY SERIES B
© 2018 Elsevier Inc. Given k pairs of vertices (si,ti)(1≤i≤k) of a digraph G, how can we test whether there exist vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 , but in  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).
Submitted to ORA: