## Abstract

The 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 [8]. Recently it was shown [3] 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 of 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 of length 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 WEAK 2-LINKAGE problem where each path P_{i} has length at most d(s_{i},t_{i})+clog^{1+ϵ}n for some constant c.

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

Journal | Theoretical Computer Science |

Volume | 814 |

Pages (from-to) | 69-73 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 24. Apr 2020 |

## Keywords

- (arc)-disjoint paths
- Acyclic digraph
- Linkage
- Shortest disjoint paths