Disjoint Paths in Decomposable Digraphs

作者：Bang Jensen Jorgen^*; Christiansen Tilde My; Maddaloni Alessandro

来源：Journal of Graph Theory, 2017, 85(2): 545-567.

DOI：10.1002/jgt.22090

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

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 is an element of [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].

• 出版日期2017-6