## Abstract

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 paths P
_{1}, P
_{2}, ,...,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].

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 85 |

Issue number | 2 |

Pages (from-to) | 545-567 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - 2017 |

## Keywords

- (round-)decomposable digraphs
- disjoint paths
- k-linkage problem
- locally semicomplete digraph
- polynomial algorithm
- quasi-transitive digraph