Disjoint Paths in Decomposable Digraphs

The k ‐linkage problem is as follows: given a digraph D = ( V , A ) and a collection of k terminal pairs( s 1 , t 1 ) , … , ( s k , t k )such that all these vertices are distinct; decide whether D has a collection of vertex disjoint pathsP 1 , P 2 , … , P ksuch that P i is from s i to t i for i ∈ [ k ] . A digraph is k ‐linked if it has a k ‐linkage for every choice of 2 k distinct vertices and every choice of k pairs as above. The k ‐linkage problem is NP‐complete already for k = 2 [11] and there exists no function f ( k ) such that every f ( k ) ‐strong digraph has a k ‐linkage for every choice of 2 k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k ‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k ‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ( 2 k − 1 ) ‐strong is also sufficient for round‐decomposable digraphs to be k ‐linked, obtaining thus a best possible bound that improves a previous one of ( 3 k − 2 ) . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].