LIPIcs.STACS.2018.26.pdf
- Filesize: 0.54 MB
- 15 pages
Document
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Authors
-
Part of:
Volume:
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-02-27
Cite AsGet BibTex
Pavel Dvorák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masarík, Tomáš Toufar, and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.STACS.2018.26
https://doi.org/10.4230/LIPIcs.STACS.2018.26
Abstract
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.
Keywords
- Steiner Tree
- Steiner Forest
- Approximation Algorithms
- Parameterized Algorithms
- Lossy Kernelization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ajit Agrawal, Philip Klein, and R. Ravi. When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. SIAM Journal on Computing, 24(3):440-456, jun 1995. URL: http://dx.doi.org/10.1137/s0097539792236237.
- 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, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250801.
- Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. On subexponential and fpt-time inapproximability. In Gregory Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 54-65. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_6.
- Glencora Borradaile, Philip N. Klein, and Claire Mathieu. An O(n log n) approximation scheme for steiner tree in planar graphs. ACM Trans. Algorithms, 5(3):31:1-31:31, 2009. URL: http://dx.doi.org/10.1145/1541885.1541892.
- Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
- 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 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, oct 2017. URL: http://dx.doi.org/10.1109/focs.2017.74.
- Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. J. Algorithms, 33(1):73-91, 1999. URL: http://dx.doi.org/10.1006/jagm.1999.1042.
- Yijia Chen and Bingkai Lin. The Constant Inapproximability of the Parameterized Dominating Set Problem. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, oct 2016. URL: http://dx.doi.org/10.1109/focs.2016.61.
- Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Directed Steiner Network Problems. arXiv preprint, 2017. URL: http://arxiv.org/abs/1707.06499.
- Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Guy Kortsarz. Fixed-parameter and approximation algorithms: A new look. In Gregory Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 110-122. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_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, Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings, volume 2368 of Lecture Notes in Computer Science, pages 170-179. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45471-3_18.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
- Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591884.
- Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. URL: http://dx.doi.org/10.1145/2650261.
- Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
- S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
- 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. arXiv preprint, 2017. URL: http://arxiv.org/abs/1710.00668v2.
- Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, and Fahad Panolan. Lossy kernels for connected dominating set on sparse graphs. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.09339.
- David Eisenstat, Philip Klein, and Claire Mathieu. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 626-638. Society for Industrial and Applied Mathematics, jan 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.53.
- 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, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 588-600. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_47.
- 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, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.27.
- Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 585-594. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780628.
- Frank K Hwang, Dana S Richards, and Pawel Winter. The Steiner tree problem, volume 53. Elsevier, 1992. URL: http://dx.doi.org/10.1016/s0167-5060(08)x7008-6.
- 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, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science, pages 671-682. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_57.
- Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Plenum, 1972. URL: http://dx.doi.org/10.1007/978-1-4684-2001-2_9.
- 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, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, volume 65 of LIPIcs, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.23.
- Michael Lampis. Parameterized approximation schemes using graph widths. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 775-786. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_64.
- Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055456.
- Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60-78, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm048.
- Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst., 43(2):234-253, 2008. URL: http://dx.doi.org/10.1007/s00224-007-9089-3.
- Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, oct 2014. URL: http://dx.doi.org/10.1109/focs.2014.37.
- Sebastian Siebertz. Lossy kernels for connected distance-r domination on nowhere dense graph classes. arXiv preprint, 2017. URL: http://arxiv.org/abs/1707.09819.
- Ondrej Suchý. Extending the kernel for planar steiner tree to the number of steiner vertices. Algorithmica, 79(1):189-210, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0249-1.
- Andreas Wiese. A (1+epsilon)-approximation for unsplittable flow on a path in fixed-parameter running time. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 67:1-67:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.67.
- David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. URL: http://dx.doi.org/10.1017/cbo9780511921735.