# Disjoint paths in unions of tournaments

Chudnovsky, M
Scott, A
Seymour, P

March 2019

## Journal:

JOURNAL OF COMBINATORIAL THEORY SERIES B

## Last Updated:

2019-09-07T00:32:41.64+01:00

135

## DOI:

10.1016/j.jctb.2018.08.007

238-255

## abstract:

© 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 [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).

910893