On hop-constrained Steiner trees in tree-like metrics. (English) Zbl 07537556
Summary: We consider the problem of computing a Steiner tree of minimum cost under a hop constraint that requires the depth of the tree to be at most \(k\). Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time \(n^{O(k)}\). For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if \(k\) is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the \(k\)-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For nonmetric graphs, we rule out an \(o(\log n)\)-approximation, assuming \(\mathrm{P} \neq \mathrm{NP}\) even when relaxing the hop constraint by any additive constant.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C05 | Trees |
| 05C12 | Distance in graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C27 | Combinatorial optimization |
References:
| [1] | I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension and provably efficient shortest path algorithms, J. ACM, 63 (2016), 41. · Zbl 1425.68447 |
| [2] | I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck, VC-dimension and shortest path algorithms, in ICALP 2011: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 6755, Springer, Berlin, 2011, pp. 690-699. · Zbl 1334.05161 |
| [3] | I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension, shortest paths, and provably efficient algorithms, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2010, pp. 782-793, https://doi.org/10.1145/2985473. · Zbl 1288.68243 |
| [4] | L. Alfandari and V. T. Paschos, Approximating minimum spanning tree of depth \(2\), Internat. Trans. Oper. Res., 6 (1999), pp. 607-622. |
| [5] | E. Althaus, S. Funke, S. Har-Peled, J. Könemann, E. A. Ramos, and M. Skutella, Approximating \(k\)-hop minimum-spanning trees, Oper. Res. Lett., 33 (2005), pp. 115-120. · Zbl 1099.90064 |
| [6] | O. Angel, A. D. Flaxman, and D. B. Wilson, A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, Combinatorica, 32 (2012), pp. 1-33. · Zbl 1299.05288 |
| [7] | S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems, J. ACM, 45 (1998), pp. 501-505. · Zbl 1065.68570 |
| [8] | S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid, Euclidean spanners: Short, thin, and lanky, in Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 489-498. · Zbl 0968.68533 |
| [9] | A. Balakrishnan and K. Altinkemer, Using a hop-constrained model to generate alternative communication network design, INFORMS J. Comput., 4 (1992), pp. 192-205. · Zbl 0825.90395 |
| [10] | J. Bar-Ilan, G. Kortsarz, and D. Peleg, Generalized submodular cover problems and applications, Theoret. Comput. Sci., 250 (2001), pp. 179-200. · Zbl 0952.68063 |
| [11] | M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2, Inform. Process. Lett., 32 (1989), pp. 171-176. · Zbl 0677.68074 |
| [12] | A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets Möbius: Fast subset convolution, in Proceedings of STOC, ACM, New York, 2007, pp. 67-74. · Zbl 1232.68188 |
| [13] | H. L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25 (1996), pp. 1305-1317, https://doi.org/10.1137/S0097539793251219. · Zbl 0864.68074 |
| [14] | P. Carmi, L. Chaitman-Yerushalmi, and O. Trabelsi, Bounded-hop communication networks, Algorithmica, 80 (2018), pp. 3050-3077. · Zbl 1410.68366 |
| [15] | M. Chimani, P. Mutzel, and B. Zey, Improved Steiner tree algorithms for bounded treewidth, J. Discrete Algorithms, 16 (2012), pp. 67-78. · Zbl 1257.05166 |
| [16] | M. Chimani and J. Spoerhase, Network design problems with bounded distances via shallow-light Steiner trees, in Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), LIPIcs. Leibniz Int. Proc. Inform. 30, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2015, pp. 238-248. · Zbl 1355.68204 |
| [17] | M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Treewidth, in Parameterized Algorithms, Springer, Cham, 2015, pp. 151-244. · Zbl 1334.90001 |
| [18] | G. Dahl, L. Gouveia, and C. Requejo, On formulations and methods for the hop-constrained minimum spanning tree problem, in Handbook of Optimization in Telecommunications, M. G. C. Resende and P. M. Pardalos, eds., Springer, Boston, MA, 2006, pp. 493-515. · Zbl 1118.90051 |
| [19] | S. E. Dreyfus and R. A. Wagner, The Steiner problem in graphs, Networks, 1 (1971), pp. 195-207. · Zbl 0229.05125 |
| [20] | M. Elkin and S. Solomon, Narrow-shallow-low-light trees with and without Steiner points, SIAM J. Discrete Math., 25 (2011), pp. 181-210, https://doi.org/10.1137/090776147. · Zbl 1227.68082 |
| [21] | J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, J. Comput. System Sci., 69 (2004), pp. 485-497. · Zbl 1071.68082 |
| [22] | A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post, A \((1+\varepsilon)\)-embedding of low highway dimension graphs into bounded treewidth graphs, SIAM J. Comput., 47 (2018), pp. 1667-1704, https://doi.org/10.1137/16M1067196. · Zbl 1398.68672 |
| [23] | L. Gouveia, Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints, Comput. Oper. Res., 22 (1995), pp. 959-970. · Zbl 0854.90139 |
| [24] | L. Gouveia, L. Simonetti, and E. Uchoa, Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs, Math. Program., 128 (2011), pp. 123-148. · Zbl 1218.90201 |
| [25] | R. L. Graham and P. Hell, On the history of the minimum spanning tree problem, IEEE Ann. Hist. Comput., 7 (1985), pp. 43-57. · Zbl 0998.68003 |
| [26] | S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, J. Algorithms, 31 (1999), pp. 228-248. · Zbl 0928.68137 |
| [27] | A. Gupta, R. Krauthgamer, and J. R. Lee, Bounded geometries, fractals, and low-distortion embeddings, in Proceedings of FOCS, IEEE, Washington, DC, 2003, pp. 534-543. |
| [28] | M. Haenggi, Twelve reasons not to route over many short hops, in Proceedings of the 60th IEEE Vehicular Technology Conference (VTC2004-Fall) (Los Angeles, CA), IEEE, Washington, DC, 2004, pp. 3130-3134. |
| [29] | B. Haeupler, D. E. Hershkowitz, and G. Zuzic, Tree embeddings for hop-constrained network design, in Proceedings of the 53rd Annual ACM SIGACT STOC, ACM, New York, 2021, pp. 356-369. · Zbl 07765177 |
| [30] | M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees, Algorithmica, 53 (2009), pp. 89-103. · Zbl 1176.68242 |
| [31] | F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem, Ann. Discrete Math. 53, North-Holland, Amsterdam, 1992. · Zbl 0774.05001 |
| [32] | V. Jarník and M. Kössler, O minimálních grafech, obsahujících \(n\) daných bod\r u, Časopis pro pěstování matematiky a fysiky, 63 (1934), pp. 223-235. · Zbl 0009.13106 |
| [33] | E. Kantor and D. Peleg, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems, J. Discrete Algorithms, 7 (2009), pp. 341-362. · Zbl 1187.68348 |
| [34] | R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, IBM Research Symposia Series, Plenum Press, New York, 1972, pp. 85-103. · Zbl 1467.68065 |
| [35] | B. Korte and J. Nešetřil, Vojtěch Jarník’s work in combinatorial optimization, Discrete Math., 235 (2001), pp. 1-17. · Zbl 1024.01018 |
| [36] | G. Kortsarz and D. Peleg, Approximating shallow-light trees, in Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 1997, pp. 103-110. · Zbl 1321.05270 |
| [37] | S. Laue and D. Matijević, Approximating k-hop minimum spanning trees in Euclidean metrics, Inform. Process. Lett., 107 (2008), pp. 96-101. · Zbl 1186.68562 |
| [38] | S. Li, A \(1.488\) approximation algorithm for the uncapacitated facility location problem, Inform. and Comput., 222 (2013), pp. 45-58. · Zbl 1281.68236 |
| [39] | P. Manyem and M. F. Stallmann, Some Approximation Results in Multicasting, Tech. report, North Carolina State University at Raleigh, Raleigh, NC, 1996. |
| [40] | D. Moshkovitz, The projection games conjecture and the NP-hardness of ln n-approximating set-cover, in APPROX-RANDOM, Lecture Notes in Comput. Sci. 7408, Springer, 2012, pp. 276-287. · Zbl 1336.68104 |
| [41] | V. R. Saksena, Topological analysis of packet networks, IEEE J. Selected Areas Commun., 7 (1989), pp. 1243-1252. |
| [42] | K. Talwar, Bypassing the embedding: Algorithms for low dimensional metrics, in Proceedings of STOC, ACM, New York, 2004, pp. 281-290. · Zbl 1192.68918 |
| [43] | S. Voß, The Steiner tree problem with hop constraints, Ann. Oper. Res., 86 (1999), pp. 321-345. · Zbl 0921.90072 |
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.
