zbMATH — the first resource for mathematics

Disjoint paths in tournaments. (English) Zbl 1304.05057
Summary: Given \( k\) pairs of vertices \((s_i, t_i)\,(1 \leq i \leq 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 \leq i \leq k\)? This is NP-complete in general digraphs, even for \(k = 2\) [S. Fortune et al., Theor. Comput. Sci. 10, 111–121 (1980; Zbl 0419.05028)], but for \(k = 2\) there is a polynomial-time algorithm when \(G\) is a tournament (or more generally, a semicomplete digraph), due to J. Bang-Jensen and C. Thomassen [SIAM J. Discrete Math. 5, No. 3, 366–376 (1992; Zbl 0759.05041)]. Here we prove that for all fixed \( k\) there is a polynomial-time algorithm to solve the problem when \(G\) is semicomplete.

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
90C39 Dynamic programming
Full Text: DOI arXiv
[1] Bang-Jensen, J.; Thomassen, C., A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM J. Discrete Math., 5, 366-376, (1992) · Zbl 0759.05041
[2] Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraphs homeomorphism problem, Theoret. Comput. Sci., 10, 111-121, (1980) · Zbl 0419.05028
[3] Fradkin, A.; Seymour, P., Edge-disjoint paths in digraphs with bounded independence number, J. Combin. Theory Ser. B, 110, 19-46, (2015) · Zbl 1302.05067
[4] Robertson, N.; Seymour, P. D., Graph minors. XIII. the disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110, (1995) · Zbl 0823.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.