Disjoint paths in tournaments

2014/11/23 by Maria Chudnovsky, Chudnovsky, Maria, Paul Seymour +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1411.6226

openalex publication_date 2014/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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, 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. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.

Related

• Disjoint paths in unions of tournaments
• Revisiting Directed Disjoint Paths on tournaments (and relatives)
• Solutions to the linkage conjecture in tournaments
• On the k-linkage problem for generalizations of semicomplete digraphs
• Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors