Disjoint paths in tournaments

DOI10.1016/J.AIM.2014.11.011zbMATH Open1304.05057arXiv1411.6226OpenAlexW1987849182MaRDI QIDQ481696FDOQ481696

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour 

Publication date: 12 December 2014

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

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.

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

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

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)

Cites Work

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

Cited In (17)

• Parity of paths in tournaments
• Path decompositions of tournaments
• DAG-width and circumference of digraphs
• 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)