The directed 2-linkage problem with length constraints (Q2304550)

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-linkage problem has been established in [\textit{S. Fortune} et al., Theor. Comput. Sci. 10, 111--121 (1980; Zbl 0419.05028)]. Several results on various variants of the weak linkage problem are discussed in [\textit{K.-I. Kawarabayashi} et al., J. Comb. Theory, Ser. B 102, No. 2, 424--435 (2012; Zbl 1298.05296); \textit{A. Björklund} and \textit{T. Husfeldt}, SIAM J. Comput. 48, No. 6, 1698--1710 (2019; Zbl 1428.05292); \textit{É. Colin de Verdière} and \textit{A. Schrijver}, ACM Trans. Algorithms 7, No. 2, Paper No. 19, 12 p. (2011; Zbl 1295.05243)]. The principal contributions of this paper are as follows: \begin{enumerate} \item FCLCUW2LP is in P when the underlying digraph is unweighted. In this case, the ``shortest'' path refers to the number of arcs between the source and sink vertices. The authors use a dynamic programming approach. Bounds are established using clever enumeration and counting. The algorithm runs in time \(O(n^{O(k)})\), where \(k = \max(k_{1}, k_{2})\). \item The variant in which one of the paths (say from \(s_{1}\) to \(t_{1}\)) is unconstrained and the other path (say from \(s_{2}\) to \(t_{2}\)) is constrained by shortest distance \(d(s_{1,}s_{2})\) is NP-hard. \item Assuming that the Exponential Time Hypothesis holds, there cannot exist a polynomial-time algorithm for the length-constrained unit weak 2-linkage problem if \(k_{1}, k_{2} = \Theta(\log^{1+ \epsilon}n)\) for every \(\epsilon > 0\), where \(n\) is the number of vertices in the input digraph. \end{enumerate} The paper articulates the principal concepts very well. In particular, the problems are clearly defined and the algorithms are clearly described. The reductions to establish lower bounds are also described well, for the most part. In particular, the reduction used to establish the non-existence of a polynomial-time algorithm for one variant via the Exponential Time Hypothesis (ETH) is very neat. There are a few issues though: \begin{enumerate} \item The presentation tends to err on the side of conciseness. A few simple figures would go a long way in clarifying the principal concepts. \item Theorem 1.2 as stated is incorrect. It is important to mention that the parameters \(a_{1}\) and \(a_{2}\) are \textit{fixed constants}, as has been indicated in [\textit{K. Bérczi} and \textit{Y. Kobayashi}, LIPIcs -- Leibniz Int. Proc. Inform. 87, Article 13, 13 p. (2017; Zbl 1445.68149)]. \item Theorem 3.2 is not self-contained. It requires some familiarity with the reduction in [\textit{S. Fortune} et al., Theor. Comput. Sci. 10, 111--121 (1980; Zbl 0419.05028)]. \end{enumerate} On the whole, the paper makes non-trivial contributions to the literature on the disjoint paths problem in directed networks.