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₁, t₁,...,(S_k, t_k) such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths P₁, P₂, ,...,P_K such 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 2k 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 2k 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 (2k-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 (3k-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].