### Abstract

Given k pairs of vertices (s_{i}, t_{i}) (1≤i≤k) of a digraph G, how can we test whether there exist k 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 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

Original language | English (US) |
---|---|

Pages (from-to) | 582-597 |

Number of pages | 16 |

Journal | Advances in Mathematics |

Volume | 270 |

DOIs | |

State | Published - Jan 2 2015 |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

### Keywords

- Disjoint paths
- Dynamic programming
- Graph
- Routing
- Tournament

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

## Cite this

Chudnovsky, M., Scott, A., & Seymour, P. (2015). Disjoint paths in tournaments.

*Advances in Mathematics*,*270*, 582-597. https://doi.org/10.1016/j.aim.2014.11.011