×

The directed 2-linkage problem with length constraints. (English) Zbl 1445.68146

This paper is concerned with a variant of the directed 2-linkage problem called the 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 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 [Y. Kobayashi and 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, N. Robertson and 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 [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 [K.-I. Kawarabayashi et al., J. Comb. Theory, Ser. B 102, No. 2, 424–435 (2012; Zbl 1298.05296); A. Björklund and T. Husfeldt, SIAM J. Comput. 48, No. 6, 1698–1710 (2019; Zbl 1428.05292); É. Colin de Verdière and 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:
1.
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})\).
2.
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.
3.
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.

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:
1.
The presentation tends to err on the side of conciseness. A few simple figures would go a long way in clarifying the principal concepts.
2.
Theorem 1.2 as stated is incorrect. It is important to mention that the parameters \(a_{1}\) and \(a_{2}\) are fixed constants, as has been indicated in [K. Bérczi and Y. Kobayashi, LIPIcs – Leibniz Int. Proc. Inform. 87, Article 13, 13 p. (2017; Zbl 1445.68149)].
3.
Theorem 3.2 is not self-contained. It requires some familiarity with the reduction in [S. Fortune et al., Theor. Comput. Sci. 10, 111–121 (1980; Zbl 0419.05028)].

On the whole, the paper makes non-trivial contributions to the literature on the disjoint paths problem in directed networks.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] (Bang-Jensen, J.; Gutin, G., Classes of Directed Graphs. Classes of Directed Graphs, Springer Monographs in Mathematics (2018), Springer Verlag: Springer Verlag London) · Zbl 1398.05002
[2] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002
[3] Bérczi, K.; Kobayashi, Y., The directed disjoint shortest paths problem, (25th Annual European Symposium on Algorithms. 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria (2017)), 13:1-13:13 · Zbl 1445.68149
[4] Björklund, A.; Husfeldt, T., Shortest two disjoint paths in polynomial time, (Automata, Languages, and Programming - 41st International Colloquium. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (2014)), 211-222 · Zbl 1398.68653
[5] Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[6] Colin de Verdière, É.; Schrijver, A., Shortest vertex-disjoint two-face paths in planar graphs, ACM Trans. Algorithms, 7, 2, 19:1-19:12 (2011) · Zbl 1295.05243
[7] Eilam-Tzoreff, T., The disjoint shortest paths problem, Discrete Appl. Math., 85, 2, 113-138 (1998) · Zbl 0902.68147
[8] Fortune, S.; Hopcroft, J. E.; Wyllie, J., The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10, 111-121 (1980) · Zbl 0419.05028
[9] Gottschau, M.; Kaiser, M.; Waldmann, C., The undirected two disjoint shortest paths problem, Oper. Res. Lett., 47, 1, 70-75 (2019) · Zbl 1476.05186
[10] Kawarabayashi, K.; Kobayashi, Y.; Reed, B. A., The disjoint paths problem in quadratic time, J. Comb. Theory, Ser. B, 102, 2, 424-435 (2012) · Zbl 1298.05296
[11] Kobayashi, Y.; Sako, R., Two disjoint shortest paths problem with non-negative edge length, Oper. Res. Lett., 47, 1, 66-69 (2019) · Zbl 1476.05188
[12] Kobayashi, Y.; Sommer, C., On shortest disjoint paths in planar graphs, Discrete Optim., 7, 4, 234-245 (2010) · Zbl 1241.90163
[13] Robertson, N.; Seymour, P. D., Graph minors. XIII: the disjoint paths problem, J. Comb. Theory, Ser. B, 63, 65-110 (1995) · Zbl 0823.05038
[14] Slivkins, A., Parameterized tractability of edge-disjoint paths on directed acyclic graphs, SIAM J. Discrete Math., 24, 1, 146-157 (2010) · Zbl 1207.68169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.