Author
Chudnovsky, M
Scott, A
Seymour, P
Journal title
Journal of Combinatorial Theory, Series B
DOI
10.1016/j.jctb.2018.08.007
Volume
135
Last updated
2024-04-14T05:33:18.13+01:00
Page
238-255
Abstract
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
Favourite
Off
Publication type
Journal Article
Publication date
05 Sep 2018
Please contact us with feedback and comments about this page. Created on 29 Aug 2018 - 09:20.