Disjoint paths in tournaments

DOI10.1016/J.AIM.2014.11.011MaRDI QIDQ481696zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Alex Scott, Paul Seymour

Publication date 12 December 2014

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.6226

zbMATH Keywords

dynamic programmingroutingdisjoint pathstournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Paths and cycles (05C38)

Abstract: Given $k$ pairs of vertices $(s_i,t_i)$, $1leilek$, of a digraph $G$, how can we test whether there exist $k$ vertex-disjoint directed paths from $s_i$ to $t_i$ for $1leilek$? 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.

Recommendations

• Disjoint paths in unions of tournaments
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Disjoint paths in decomposable digraphs
• scientific article; zbMATH DE number 4085689

Cites work

• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Edge-disjoint paths in digraphs with bounded independence number
• Graph minors. XIII: The disjoint paths problem
• The directed subgraph homeomorphism problem

Cited in

(17)

• Parity of paths in tournaments
• DAG-width and circumference of digraphs
• Path decompositions of tournaments
• Lexicographic orientation algorithms
• Paths with many shortcuts in tournaments
• What's next? Future directions in parameterized complexity
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• On the pathwidth of almost semicomplete digraphs
• Polynomial time algorithms for tracking path problems
• On width measures and topological problems on semi-complete digraphs
• Tournament pathwidth and topological containment
• Disjoint paths in decomposable digraphs
• Tournaments and Semicomplete Digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Digraphs of bounded width
• Polynomial Time Algorithms for Tracking Path Problems
• Disjoint paths in unions of tournaments

This page was built for publication: Disjoint paths in tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q481696)