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
Submitted to ORA
On
Favourite
Off
Publication type
Journal Article
Publication date
05 Sep 2018