The directed 2-linkage problem with length constraints
type: Item
instance of: scholarly article
title: The directed 2-linkage problem with length constraints
zbMATH Open document ID: 1445.68146
author: Thomas Bellitto
author: William Lochet
author: A. Yeo
author: Jørgen Bang-Jensen
published in: Theoretical Computer Science
publication date: 2020-03-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/1907.00817
review text: This paper is concerned with a variant of the directed 2-linkage problem called the \textit{weak linkage} problem. In the directed 2-linkage problem, we are given a digraph \(G= \langle V, E \rangle\) and vertices \(s_{1}, t_{1}, s_{2}, t_{2} \in V\) and asked if there exists a vertex-disjoint pair of paths connecting \(s_{1}\) to \(t_{1}\) and \(s_{2}\) to \(t_{2}\). In the \textit{weak linkage} problem, the paths between \(s_{i}\) and \(t_{i}\) are required to be arc-disjoint. In the variant studied in this paper, the standard weak \(2\)-linkage problem is augmented with length constraints. Accordingly, we are given a digraph \(G= \langle V, E_\mathbf{w} \rangle\) with non-negative weights on the arcs and the goal is to find arc-disjoint paths between \(s_{i}\) and \(t_{i}\) subject to a length criterion on the paths. If the arc-weights are all the unity, the problem is referred to as the unit weak 2-linkage problem. In the \((k_{1}, k_{2})\) constrained version of the unit weak 2-linkage problem, we are given constants \(k_{1}\) and \(k_{2}\) and the goal is to find the paths from \(s_{i}\) to \(t_{i}\) of length at most \(d(s_{i}, t_{i})+k_{i}\), where \(d(s_{i}, t_{i})\) refers to the shortest path from \(s_{i}\) to \(t_{i}\). We refer to the last problem as fixed constant-length constrained unit weak 2-linkage problem (FCLCUW2LP). Variants of the linkage and weak linkage problems have been studied extensively in the literature [\textit{Y. Kobayashi} and \textit{C. Sommer}, Discrete Optim. 7, No. 4, 234--245 (2010; Zbl 1241.90163)]. The linkage and weak linkage problems are polynomially equivalent. The complexities of linkage problems depend on whether the underlying graph is directed or undirected. For the undirected case, \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 63, No. 1, 65--110 (1995; Zbl 0823.05038)] showed that the \(k\)-linkage problem is fixed-parameter tractable in \(k\). For the directed case, the NP-hardness of the 2…
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7179872
zbMATH Keywords: (arc)-disjoint paths
zbMATH Keywords: shortest disjoint paths
zbMATH Keywords: acyclic digraph
zbMATH Keywords: linkage
reviewed by: K. Subramani
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2999386390
arXiv ID: 1907.00817
cites work: Classes of Directed Graphs
cites work: Digraphs
cites work: The Directed Disjoint Shortest Paths Problem
cites work: Shortest Two Disjoint Paths in Polynomial Time
cites work: Parameterized Algorithms
cites work: Shortest vertex-disjoint two-face paths in planar graphs
cites work: The disjoint shortest paths problem
cites work: The directed subgraph homeomorphism problem
cites work: The undirected two disjoint shortest paths problem
cites work: The disjoint paths problem in quadratic time
cites work: Two disjoint shortest paths problem with non-negative edge length
cites work: On shortest disjoint paths in planar graphs
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
Wikidata QID: Q126344620
DOI: 10.1016/J.TCS.2020.01.012
description: scientific article