Disjoint paths in unions of tournaments

Author: 

Chudnovsky, M
Scott, A
Seymour, P

Publication Date: 

March 2019

Journal: 

JOURNAL OF COMBINATORIAL THEORY SERIES B

Last Updated: 

2019-04-25T09:56:58.027+01:00

Volume: 

135

DOI: 

10.1016/j.jctb.2018.08.007

page: 

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

Symplectic id: 

910893

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article