cs.CC cs.DM cs.DS
The directed 2 linkage problem with length constraints. The sc weak 2 linkage problem for digraphs asks for a given digraph and vertices s 1,s 2,t 1,t 2 whether D contains a pair of arc disjoint paths P 1,P 2 such that P i is an (s i,t i) path. This problem is NP complete for general digraphs but polynomially solvable for acyclic digraphs cite fortuneTCS10 . Recently it was shown cite bercziESA17 that if D is equipped with a weight function w on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak 2 linkage problem when both paths have to be shortest paths in D . In this paper we consider the unit weight case and prove that for every pair constants k 1,k 2 , there is a polynomial algorithm which decides whether the input digraph D has a pair of arc disjoint paths P 1,P 2 such that P i is an (s i,t i) path and the length of P i is no more than d(s i,t i) k i , for i 1,2 , where d(s i,t i) denotes the length of the shortest (s i,t i) path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P 1,P 2 to the sc weak 2 linkage problem where each path P i has length at most d(s i,t i) c log 1 epsilon n for some constant c . We also prove that the sc weak 2 linkage problem remains NP complete if we require one of the two paths to be a shortest path while the other path has no restriction on the length.