Disjoint paths in unions of tournaments

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)238-255
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume135
DOIs
StatePublished - 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