The directed 2-linkage problem with length constraints

J. Bang-Jensen*, T. Bellitto, W. Lochet, A. Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The WEAK 2-LINKAGE problem for digraphs asks for a given digraph and vertices s1,s2,t1,t2 whether D contains a pair of arc-disjoint paths P1,P2 such that Pi is an (si,ti)-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 k1,k2, there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P1,P2 such that Pi is an (si,ti)-path of length no more than d(si,ti)+ki, for i=1,2, where d(si,ti) denotes the length of the shortest (si,ti)-path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P1,P2 to the WEAK 2-LINKAGE problem where each path Pi has length at most d(si,ti)+clog1+ϵ⁡n for some constant c.

Original languageEnglish
JournalTheoretical Computer Science
Volume814
Pages (from-to)69-73
ISSN0304-3975
DOIs
Publication statusAccepted/In press - 1. Jan 2020

    Fingerprint

Keywords

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

Cite this