Parameterized approximation schemes for Steiner trees with small number of Steiner vertices. (English) Zbl 1487.68175
Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 26, 15 p. (2018).
Summary: We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter.
We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For neither of these an EPAS is likely to exist for the studied parameter: for Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
For the entire collection see [Zbl 1381.68010].
We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For neither of these an EPAS is likely to exist for the studied parameter: for Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
For the entire collection see [Zbl 1381.68010].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C05 | Trees |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68W25 | Approximation algorithms |
Keywords:
Steiner tree; Steiner forest; approximation algorithms; parameterized algorithms; lossy kernelizationReferences:
| [1] | Ajit Agrawal, Philip Klein, and R. Ravi. When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. {\it SIAM Journal on Computing}, 24(3):440- 456, jun 1995. doi:10.1137/s0097539792236237. · Zbl 0831.68071 |
| [2] | Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: fast subset convolution. In David S. Johnson and Uriel Feige, editors, {\it Proceedings} {\it of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA,} {\it June 11-13, 2007}, pages 67-74. ACM, 2007. doi:10.1145/1250790.1250801. · Zbl 1232.68188 |
| [3] | Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. On subexponential and fpt-time inapproximability. In Gregory Gutin and Stefan Szeider, editors, {\it Pa-} {\it rameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia An-} {\it tipolis, France, September 4-6, 2013, Revised Selected Papers}, volume 8246 of {\it Lecture Notes} {\it in Computer Science}, pages 54-65. Springer, 2013. doi:10.1007/978-3-319-03898-8_6. · Zbl 1309.68229 |
| [4] | Glencora Borradaile, Philip N. Klein, and Claire Mathieu. An {\it O}({\it n }log {\it n}) approximation scheme for steiner tree in planar graphs. {\it ACM Trans. Algorithms}, 5(3):31:1-31:31, 2009. doi:10.1145/1541885.1541892. · Zbl 1300.05294 |
| [5] | Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità.Steiner tree approximation via iterative randomized rounding. {\it J. ACM}, 60(1):6:1-6:33, 2013. doi: 10.1145/2432622.2432628. · Zbl 1281.68234 |
| [6] | Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manuran gsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. In {\it 2017 IEEE 58th Annual Symposium on Foundations} {\it of Computer Science (FOCS)}. IEEE, oct 2017. doi:10.1109/focs.2017.74. |
| [7] | Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. {\it J. Algorithms}, 33(1):73-91, 1999. doi:10.1006/jagm.1999.1042. · Zbl 0937.68155 |
| [8] | Yijia Chen and Bingkai Lin. The Constant Inapproximability of the Parameterized Dominating Set Problem. In {\it 2016 IEEE 57th Annual Symposium on Foundations of Computer} {\it Science (FOCS)}. IEEE, oct 2016. doi:10.1109/focs.2016.61. |
| [9] | Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi.Parameterized Approximation Algorithms for Directed Steiner Network Problems.{\it arXiv preprint}, 2017. arXiv:1707.06499. |
| [10] | Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Guy Kortsarz. Fixed-parameter and approximation algorithms: A new look. In Gregory Gutin and Stefan Szeider, editors, {\it Parameterized and Exact Computation - 8th International Symposium, IPEC 2013,} {\it Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers}, volume 8246 of {\it Lecture Notes in Computer Science}, pages 110-122. Springer, 2013.doi:10.1007/ 978-3-319-03898-8_11. · Zbl 1407.68213 |
| [11] | Miroslav Chlebík and Janka Chlebíková. Approximation hardness of the steiner tree problem on graphs. In Martti Penttonen and Erik Meineche Schmidt, editors, {\it Algorithm Theory} · Zbl 1078.68637 |
| [12] | Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. {\it Parameterized Algorithms}. Springer, 2015. doi:10.1007/978-3-319-21275-3. · Zbl 1334.90001 |
| [13] | Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, {\it Symposium on Theory of Computing, STOC 2014, New York, NY, USA,} {\it May 31 - June 03, 2014}, pages 624-633. ACM, 2014. doi:10.1145/2591796.2591884. · Zbl 1315.91001 |
| [14] | Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. {\it ACM Trans. Algorithms}, 11(2):13:1-13:20, 2014. doi:10.1145/2650261. · Zbl 1398.68226 |
| [15] | Rodney G. Downey and Michael R. Fellows. {\it Parameterized Complexity}. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9. |
| [16] | S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. {\it Networks}, 1(3):195-207, 1971. doi:10.1002/net.3230010302. · Zbl 0229.05125 |
| [17] | Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. {\it arXiv preprint}, 2017. arXiv:1710.00668v2. |
| [18] | Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, and Fahad Panolan. Lossy kernels for connected dominating set on sparse graphs. {\it arXiv preprint}, 2017. arXiv:1706.09339. |
| [19] | David Eisenstat, Philip Klein, and Claire Mathieu. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In {\it Proceedings of the Twenty-Third Annual} {\it ACM-SIAM Symposium on Discrete Algorithms}, pages 626-638. Society for Industrial and Applied Mathematics, jan 2012. doi:10.1137/1.9781611973099.53. · Zbl 1421.68214 |
| [20] | Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low highway dimension graphs. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, {\it Automata, Languages, and Programming - 42nd Inter-} {\it national Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part} {\it II}, volume 9135 of {\it Lecture Notes in Computer Science}, pages 588-600. Springer, 2015. doi:10.1007/978-3-662-47666-6_47. · Zbl 1404.68209 |
| [21] | Andreas Emil Feldmann and Dániel Marx. The complexity landscape of fixed-parameter directed steiner network problems. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, {\it 43rd International Colloquium on Automata,} {\it Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy}, volume 55 of {\it LIPIcs}, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.27. · Zbl 1388.68228 |
| [22] | Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Lawrence L. Larmore and Michel X. Goemans, editors, {\it Proceedings of the 35th Annual ACM Symposium} {\it on Theory of Computing, June 9-11, 2003, San Diego, CA, USA}, pages 585-594. ACM, 2003. doi:10.1145/780542.780628. · Zbl 1192.68321 |
| [23] | Frank K Hwang, Dana S Richards, and Pawel Winter. {\it The Steiner tree problem}, volume 53. Elsevier, 1992. doi:10.1016/s0167-5060(08)x7008-6. · Zbl 0774.05001 |
| [24] | Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Ondrej Suchý. Parameterized complexity of directed steiner tree on sparse graphs. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, {\it Algorithms - ESA 2013 - 21st Annual European Symposium,} {\it Sophia Antipolis, France, September 2-4, 2013. Proceedings}, volume 8125 of {\it Lecture Notes in} {\it Computer Science}, pages 671-682. Springer, 2013. doi:10.1007/978-3-642-40450-4_57. · Zbl 1371.68114 |
| [25] | Richard M. Karp. Reducibility among combinatorial problems. In {\it Complexity of computer} {\it computations}, pages 85-103. Plenum, 1972. doi:10.1007/978-1-4684-2001-2_9. · Zbl 1467.68065 |
| [26] | :14 |
| [27] | R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale.Lossy kernels for graph contraction problems. In Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen, editors, {\it 36th IARCS Annual Conference on Foundations of Software Technology and} {\it Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India}, volume 65 of {\it LIPIcs}, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.FSTTCS.2016.23. · Zbl 1391.68059 |
| [28] | :15 |
| [29] | Michael Lampis. Parameterized approximation schemes using graph widths. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, {\it Automata,} {\it Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen,} {\it Denmark, July 8-11, 2014, Proceedings, Part I}, volume 8572 of {\it Lecture Notes in Computer} {\it Science}, pages 775-786. Springer, 2014. doi:10.1007/978-3-662-43948-7_64. · Zbl 1410.68402 |
| [30] | Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, {\it Proceedings of the 49th} {\it Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC,} {\it Canada, June 19-23, 2017}, pages 224-237. ACM, 2017. doi:10.1145/3055399.3055456. · Zbl 1370.68136 |
| [31] | Dániel Marx.Parameterized complexity and approximation algorithms.{\it Comput. J.}, 51(1):60-78, 2008. doi:10.1093/comjnl/bxm048. |
| [32] | Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. {\it Theory Comput. Syst.}, 43(2):234-253, 2008. doi:10.1007/s00224-007-9089-3. · Zbl 1148.68041 |
| [33] | Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. In {\it 2014 IEEE} {\it 55th Annual Symposium on Foundations of Computer Science}. IEEE, oct 2014. doi:10. 1109/focs.2014.37. |
| [34] | Sebastian Siebertz. Lossy kernels for connected distance-{\it r }domination on nowhere dense graph classes. {\it arXiv preprint}, 2017. arXiv:1707.09819. |
| [35] | Ondrej Suchý. Extending the kernel for planar steiner tree to the number of steiner vertices. {\it Algorithmica}, 79(1):189-210, 2017. doi:10.1007/s00453-016-0249-1. · Zbl 1372.68146 |
| [36] | Andreas Wiese. A (1+epsilon)-approximation for unsplittable flow on a path in fixedparameter running time. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, {\it 44th International Colloquium on Automata, Languages, and Program-} {\it ming, ICALP 2017, July 10-14, 2017, Warsaw, Poland}, volume 80 of {\it LIPIcs}, pages 67:1- 67:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. doi:10.4230/LIPIcs. ICALP.2017.67. · Zbl 1441.68291 |
| [37] | David P Williamson and David B Shmoys. {\it The design of approximation algorithms}. Cambridge university press, 2011. doi:10.1017/cbo9780511921735. · Zbl 1219.90004 |
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.
