Disjoint paths in unions of tournaments

摘要

Given k pairs of vertices (s(i), t(i)) (1 = i = k) of a digraph G, how can we test whether there exist vertex-disjoint directed paths from s, to t, for 1 = i = k? This is NP-complete in general digraphs, even for k = 2 [4], but in [3] 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). (C) 2018 Elsevier Inc. All rights reserved.