### Abstract

Given k pairs of vertices (s_{i},t_{i})(1≤i≤k) of a digraph G, how can we test whether there exist vertex-disjoint directed paths from s_{i} to t_{i} 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 | English (US) |
---|---|

Pages (from-to) | 238-255 |

Number of pages | 18 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 135 |

DOIs | |

State | Published - Mar 2019 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

### Keywords

- Algorithm
- Directed graph
- Disjoint paths
- Tournament

## Fingerprint Dive into the research topics of 'Disjoint paths in unions of tournaments'. Together they form a unique fingerprint.

## Cite this

Chudnovsky, M., Scott, A., & Seymour, P. (2019). Disjoint paths in unions of tournaments.

*Journal of Combinatorial Theory. Series B*,*135*, 238-255. https://doi.org/10.1016/j.jctb.2018.08.007