Disjoint Paths in Decomposable Digraphs |
| |
| Authors: | Jørgen Bang‐Jensen Tilde My Christiansen Alessandro Maddaloni |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, UNIVERSITY OF SOUTHERN DENMARK, ODENSE, DENMARK;2. TECIP INSTITUTE, SCUOLA SUPERIORE SANT'ANNA, PISA, ITALY |
| |
| Abstract: | The k‐linkage problem is as follows: given a digraph  and a collection of k terminal pairs  such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths  such that  is from  to  for  . 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  11] and there exists no function  such that every  ‐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  ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of  . 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]. |
| |
| Keywords: | disjoint paths locally semicomplete digraph quasi‐transitive digraph k‐linkage problem (round‐)decomposable digraphs polynomial algorithm |
|
|
and a collection of k terminal pairs 
such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths 
such that 
is from 
to 
for 
. 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 
11] and there exists no function 
such that every 
‐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 
‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of 
. 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].