Parameterized approximation schemes for Steiner trees with small number of Steiner vertices. (English) Zbl 1462.68138
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 parameterization. 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 nonterminals (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 none of these is an EPAS 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 approximating within any function of the studied parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree, but a PSAKS does not. We also 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.
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 |
Software:
GitHubReferences:
| [1] | A. Agrawal, P. Klein, and R. Ravi, When trees collide: An approximation algorithm for the generalized steiner problem on networks, SIAM J. Comput., 24 (1995), pp. 440-456, https://doi.org/10.1137/s0097539792236237. · Zbl 0831.68071 |
| [2] | A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets Möbius: Fast subset convolution, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, https://doi.org/10.1145/1250790.1250801. · Zbl 1232.68188 |
| [3] | É. Bonnet and F. Sikora, The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration, in 13th International Symposium on Parameterized and Exact Computation, LIPIcs Leibniz Int. Proc. Inform. 115, C. Paul and M. Pilipczuk, eds., Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2019, pp. 26:1-26:15, https://doi.org/10.4230/LIPIcs.IPEC.2018.26. · Zbl 1520.68114 |
| [4] | A. Borchers and D.-Z. Du, The \(k\)-Steiner ratio in graphs, SIAM J. Comput., 26 (1997), pp. 857-869, https://doi.org/10.1137/S0097539795281086. · Zbl 0870.68109 |
| [5] | G. Borradaile, P. Klein, and C. Mathieu, An O(n log n) approximation scheme for Steiner tree in planar graphs, ACM Trans. Algorithms, 5 (2009), pp. 1-31, https://doi.org/10.1145/1541885.1541892. · Zbl 1300.05294 |
| [6] | J. Byrka, F. Grandoni, T. Rothvoss, and L. Sanità, Steiner tree approximation via iterative randomized rounding, J. ACM, 60 (2013), pp. 1-33, https://doi.org/10.1145/2432622.2432628. · Zbl 1281.68234 |
| [7] | M. Charikar, C. Chekuri, T. yat Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Approximation algorithms for directed steiner problems, J. Algorithms, 33 (1999), pp. 73-91, https://doi.org/10.1006/jagm.1999.1042. · Zbl 0937.68155 |
| [8] | R. Chitnis, M. T. Hajiaghayi, and G. Kortsarz, Fixed-parameter and approximation algorithms: A new look, in Parameterized and Exact Computation, Springer, New York, 2013, pp. 110-122, https://doi.org/10.1007/978-3-319-03898-8_11. · Zbl 1407.68213 |
| [9] | R. Chitnis, A. E. Feldmann, and P. Manurangsi, Parameterized approximation algorithms for bidirected Steiner network problems, in 26th Annual European Symposium on Algorithms, LIPIcs Leibniz Int. Proc. Inform. 112, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, pp. 20:1-20:16, https://doi.org/10.4230/LIPIcs.ESA.2018.20. · Zbl 1522.68395 |
| [10] | M. Chlebík and J. Chlebíková, Approximation hardness of the steiner tree problem on graphs, in Algorithm Theory-SWAT 2002, Springer, Berlin, 2002, pp. 170-179, https://doi.org/10.1007/3-540-45471-3_18. · Zbl 1078.68637 |
| [11] | M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, New York, 2015, https://doi.org/10.1007/978-3-319-21275-3. · Zbl 1334.90001 |
| [12] | I. Dinur and D. Steurer, Analytical approach to parallel repetition, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 2014, https://doi.org/10.1145/2591796.2591884. · Zbl 1315.91001 |
| [13] | M. Dom, D. Lokshtanov, and S. Saurabh, Kernelization lower bounds through colors and IDs, ACM Trans. Algorithms, 11 (2014), pp. 1-20, https://doi.org/10.1145/2650261. · Zbl 1398.68226 |
| [14] | R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer, New York, 1999, https://doi.org/10.1007/978-1-4612-0515-9. · Zbl 0961.68533 |
| [15] | S. E. Dreyfus and R. A. Wagner, The steiner problem in graphs, Networks, 1 (1971), pp. 195-207, https://doi.org/10.1002/net.3230010302. · Zbl 0229.05125 |
| [16] | D. Eisenstat, P. Klein, and C. Mathieu, An efficient polynomial-time approximation scheme for steiner forest in planar graphs, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2012, pp. 626-638, https://doi.org/10.1137/1.9781611973099.53. · Zbl 1421.68214 |
| [17] | A. E. Feldmann and D. Marx, The complexity landscape of fixed-parameter directed Steiner network problems, in 43rd International Colloquium on Automata, Languages, and Programming, LIPIcs Leibniz Int. Proc. Inform. 55, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2016, pp. 27:1-27:14, https://doi.org/10.4230/LIPIcs.ICALP.2016.27. · Zbl 1388.68228 |
| [18] | B. Fuchs, W. Kern, D. Molle, S. Richter, P. Rossmanith, and X. Wang, Dynamic programming for minimum Steiner trees, Theory Comput. Syst., 41 (2007), pp. 493-500, https://doi.org/10.1007/s00224-007-1324-4. · Zbl 1148.68038 |
| [19] | J. Guo, R. Niedermeier, and O. Suchý, Parameterized complexity of arc-weighted directed Steiner problems, SIAM J. Discrete Math., 25 (2011), pp. 583-599, https://doi.org/10.1137/100794560. · Zbl 1230.05268 |
| [20] | E. Halperin and R. Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th ACM Symposium on Theory of Computing, 2003, pp. 585-594, https://doi.org/10.1145/780542.780628. · Zbl 1192.68321 |
| [21] | R. Hušek, T. Toufar, D. Knop, T. Masařík, and E. Eiben, Steiner Tree Heuristics for PACE 2018 Challenge Track C, https://github.com/goderik01/PACE2018, 2018. |
| [22] | R. Hušek, D. Knop, and T. Masařík, Approximation algorithms for Steiner tree based on star contractions: A unified view, in Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020, pp. 16:1-16:18, https://doi.org/10.4230/LIPIcs.IPEC.2020.16. · Zbl 07764107 |
| [23] | F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem, Ann. Discrete Math. 53, Elsevier, Amsterdam, 1992, https://doi.org/10.1016/s0167-5060(08)x7008-6. · Zbl 0774.05001 |
| [24] | M. Jones, D. Lokshtanov, M. S. Ramanujan, S. Saurabh, and O. Suchý, Parameterized complexity of directed Steiner tree on sparse graphs, SIAM J. Discrete Math., 31 (2017), pp. 1294-1327, https://doi.org/10.1137/15M103618X. · Zbl 1371.68115 |
| [25] | R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Plenum, New York, 1972, pp. 85-103, https://doi.org/10.1007/978-1-4684-2001-2_9. · Zbl 1467.68065 |
| [26] | D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh, Lossy kernelization, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 224-237, https://doi.org/10.1145/3055399.3055456. · Zbl 1370.68136 |
| [27] | D. Mölle, S. Richter, and P. Rossmanith, Enumerate and expand: Improved algorithms for connected vertex cover and tree cover, Theory Comput. Syst., 43 (2007), pp. 234-253, https://doi.org/10.1007/s00224-007-9089-3. · Zbl 1148.68041 |
| [28] | J. Nederlof, Fast polynomial-space algorithms using möbius inversion: Improving on Steiner tree and related problems, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Rhodes, Greece, Part I, 2009, pp. 713-725, https://doi.org/10.1007/978-3-642-02927-1_59. · Zbl 1248.68258 |
| [29] | M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen, Network sparsification for Steiner problems on planar and bounded-genus graphs, in Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, https://doi.org/10.1109/focs.2014.37. · Zbl 1454.68114 |
| [30] | K. C. Srikanta, B. Laekhanukit, and P. Manurangsi, On the parameterized complexity of approximating dominating set, J. ACM, 66 (2019), https://doi.org/10.1145/3325116. · Zbl 1473.68099 |
| [31] | O. Suchý, Extending the kernel for planar Steiner tree to the number of steiner vertices, Algorithmica, 79 (2017), pp. 189-210, https://doi.org/10.1007/s00453-016-0249-1. · Zbl 1372.68146 |
| [32] | D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, Cambridge, UK, 2011, https://doi.org/10.1017/cbo9780511921735. · Zbl 1219.90004 |
| [33] | A. Zelikovsky, An 11/6-approximation algorithm for the network Steiner problem, Algorithmica, 9 (1993), pp. 463-470, https://doi.org/10.1007/BF01187035. · Zbl 0768.68192 |
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.
