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).
Original language | American English |
---|---|
Pages (from-to) | 238-255 |
Number of pages | 18 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 135 |
DOIs | |
State | Published - Mar 2019 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Algorithm
- Directed graph
- Disjoint paths
- Tournament