{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:56:05Z","timestamp":1787324165181,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/18m1209489","type":"journal-article","created":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T10:54:32Z","timestamp":1617015272000},"page":"546-574","source":"Crossref","is-referenced-by-count":7,"title":["Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices"],"prefix":"10.1137","volume":"35","author":[{"given":"Pavel","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas E.","family":"Feldmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":true,"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":true,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1\u0161","family":"Toufar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski, and M. Koivisto,\n                      Fourier meets M\u00f6bius: Fast subset convolution\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007,https:\/\/doi.org\/10.1145\/1250790.1250801.","DOI":"10.1145\/1250790.1250801"},{"key":"atypb3","unstructured":"\u00c9. Bonnet and F. Sikora,\n                      The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration\n                      , 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\u00fcr Informatik, Dagstuhl, Germany, 2019, pp. 26:1-26:15,https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.26."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"atypb8","first-page":"110","author":"Chitnis R.","year":"2013","journal-title":"New York"},{"key":"atypb9","first-page":"1","author":"Chitnis R.","year":"2018","journal-title":"Germany"},{"key":"atypb10","first-page":"170","author":"Chleb\u00edk M.","year":"2002","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"I. Dinur and D. Steurer,\n                      Analytical approach to parallel repetition\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 2014,https:\/\/doi.org\/10.1145\/2591796.2591884.","DOI":"10.1145\/2591796.2591884"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer, New York, 1999,https:\/\/doi.org\/10.1007\/978-1-4612-0515-9.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"atypb16","first-page":"626","author":"Eisenstat D.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"1","author":"Feldmann A. E.","year":"2016","journal-title":"Germany"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/100794560"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"E. Halperin and R. Krauthgamer,\n                      Polylogarithmic inapproximability\n                      , in Proceedings of the 35th ACM Symposium on Theory of Computing, 2003, pp. 585-594,https:\/\/doi.org\/10.1145\/780542.780628.","DOI":"10.1145\/780542.780628"},{"key":"atypb21","unstructured":"R. Hu\u0161ek, T. Toufar, D. Knop, T. Masa\u0159\u00edk, and E. Eiben,\n                      Steiner Tree Heuristics for PACE\n                      2018\n                      Challenge Track\n                      C,https:\/\/github.com\/goderik01\/PACE2018, 2018."},{"key":"atypb22","first-page":"16","author":"Hu\u0161ek R.","year":"2020","journal-title":"IPEC."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"F. K. Hwang, D. S. Richards, and P. Winter,\n                      The Steiner Tree Problem\n                      , Ann. Discrete Math. 53, Elsevier, Amsterdam, 1992,https:\/\/doi.org\/10.1016\/s0167-5060(08)x7008-6.","DOI":"10.1016\/S0167-5060(08)X7008-6"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/15M103618X"},{"key":"atypb25","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh,\n                      Lossy kernelization\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 224-237,https:\/\/doi.org\/10.1145\/3055399.3055456.","DOI":"10.1145\/3055399.3055456"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9089-3"},{"key":"atypb28","first-page":"713","author":"Nederlof J.","year":"2009","journal-title":"Part"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen,\n                      Network sparsification for Steiner problems on planar and bounded-genus graphs\n                      , in Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, 2014,https:\/\/doi.org\/10.1109\/focs.2014.37.","DOI":"10.1109\/FOCS.2014.37"},{"key":"atypb30","first-page":"10","volume":"66","author":"Srikanta K. C.","year":"2019","journal-title":"J. ACM"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0249-1"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"D. P. Williamson and D. B. Shmoys,\n                      The Design of Approximation Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2011,https:\/\/doi.org\/10.1017\/cbo9780511921735.","DOI":"10.1017\/CBO9780511921735"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"A. Zelikovsky,\n                      An 11\/6-approximation algorithm for the network Steiner problem\n                      , Algorithmica, 9 (1993), pp. 463-470,https:\/\/doi.org\/10.1007\/BF01187035.","DOI":"10.1007\/BF01187035"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1209489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:43Z","timestamp":1787321983000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1209489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/18M1209489"],"URL":"https:\/\/doi.org\/10.1137\/18m1209489","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}