{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:32:39Z","timestamp":1770489159359,"version":"3.49.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T00:00:00Z","timestamp":1537142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704 and 677651"],"award-info":[{"award-number":["714704 and 677651"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["259515 and 267959"],"award-info":[{"award-number":["259515 and 267959"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"\n We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph\n G<\/jats:italic>\n embedded on a surface of genus\n g<\/jats:italic>\n and a designated face\n f<\/jats:italic>\n bounded by a simple cycle of length\n k<\/jats:italic>\n , uncovers a set\n F<\/jats:italic>\n \u2286\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ) of size polynomial in\n g<\/jats:italic>\n and\n k<\/jats:italic>\n that contains an optimal Steiner tree for\n any<\/jats:italic>\n set of terminals that is a subset of the vertices of\n f<\/jats:italic>\n .\n <\/jats:p>\n We apply this general theorem to prove that:<\/jats:p>\n \n \u2014 Given an unweighted graph\n G<\/jats:italic>\n embedded on a surface of genus\n g<\/jats:italic>\n and a terminal set\n S<\/jats:italic>\n \u2286\n V<\/jats:italic>\n (\n G<\/jats:italic>\n ), one can in polynomial time find a set\n F<\/jats:italic>\n \u2286\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ) that contains an optimal Steiner tree\n T<\/jats:italic>\n for\n S<\/jats:italic>\n and that has size polynomial in\n g<\/jats:italic>\n and |\n E<\/jats:italic>\n (\n T<\/jats:italic>\n )|.\n <\/jats:p>\n \n \u2014 An analogous result holds for an optimal Steiner forest for a set\n S<\/jats:italic>\n of terminal pairs.\n <\/jats:p>\n \n \u2014 Given an unweighted planar graph\n G<\/jats:italic>\n and a terminal set\n S<\/jats:italic>\n \u2286\n V<\/jats:italic>\n (\n G<\/jats:italic>\n ), one can in polynomial time find a set\n F<\/jats:italic>\n \u2286\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ) that contains an optimal (edge) multiway cut\n C<\/jats:italic>\n separating\n S<\/jats:italic>\n (i.e., a cutset that intersects any path with endpoints in different terminals from\n S<\/jats:italic>\n ) and that has size polynomial in |\n C<\/jats:italic>\n |.\n <\/jats:p>\n \n In the language of parameterized complexity, these results imply the first polynomial kernels for S\n teiner<\/jats:sc>\n T\n ree<\/jats:sc>\n and S\n teiner<\/jats:sc>\n F\n orest<\/jats:sc>\n on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E\n dge<\/jats:sc>\n ) M\n ultiway<\/jats:sc>\n C\n ut<\/jats:sc>\n on planar graphs (parameterized by the size of the cutset).\n <\/jats:p>\n \n Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph\n G<\/jats:italic>\n with positive edge weights, a designated face\n f<\/jats:italic>\n bounded by a simple cycle of weight\n w<\/jats:italic>\n (\n f<\/jats:italic>\n ), and an accuracy parameter \u03b5 > 0, uncovers a set\n F<\/jats:italic>\n \u2286\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ) of total weight at most poly(\u03b5\n -1<\/jats:sup>\n )\n w<\/jats:italic>\n (\n f<\/jats:italic>\n ) that, for any set of terminal pairs that lie on\n f<\/jats:italic>\n , contains a Steiner forest within additive error \u03b5\n w<\/jats:italic>\n (\n f<\/jats:italic>\n ) from the optimal Steiner forest.\n <\/jats:p>","DOI":"10.1145\/3239560","type":"journal-article","created":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T12:14:54Z","timestamp":1537186494000},"page":"1-73","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs"],"prefix":"10.1145","volume":"14","author":[{"given":"Marcin","family":"Pilipczuk","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan Van","family":"Leeuwen","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095170"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9662-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-17-1-152-170"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00353-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_2_1_19_1","volume-title":"Open problems from Workshop on Kernels. Retrieved on","author":"Cygan Marek","year":"2018","unstructured":"Marek Cygan, \u0141ukasz Kowalik, and Marcin Pilipczuk. 2013. Open problems from Workshop on Kernels. Retrieved on September 3, 2018 from http:\/\/worker2013.mimuw.edu.pl\/slides\/worker-opl.pdf."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_22_1","volume-title":"Demaine and MohammadTaghi Hajiaghayi","author":"Erik","year":"2008","unstructured":"Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008. Bidimensionality. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"e_1_2_1_25_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel. 2005. Graph Theory. Springer."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778635"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464827"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488702"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095169"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794269072"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2783147.2783151"},{"key":"e_1_2_1_37_1","first-page":"26","article-title":"Data reduction and problem kernels (Dagstuhl Seminar 12241)","volume":"2","author":"Fellows Michael R.","year":"2012","unstructured":"Michael R. Fellows, Jiong Guo, D\u00e1niel Marx, and Saket Saurabh. 2012. Data reduction and problem kernels (Dagstuhl Seminar 12241). Dagstuhl Reports 2, 6 (2012), 26--50.","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1941886"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873644"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_43_1","volume-title":"Improved guarantees for vertex sparsification in planar graphs. CoRR abs\/1702.01136","author":"Goranci Gramoz","year":"2017","unstructured":"Gramoz Goranci, Monika Henzinger, and Pan Peng. 2017. Improved guarantees for vertex sparsification in planar graphs. CoRR abs\/1702.01136 (2017). http:\/\/arxiv.org\/abs\/1702.01136"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1592"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_2_1_48_1","unstructured":"Bart M. P. Jansen Marcin Pilipczuk and Erik Jan van Leeuwen. 2018. A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs manuscript."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070454"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132620"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009223"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627945"},{"key":"e_1_2_1_58_1","volume-title":"Refined vertex sparsifiers of planar graphs. CoRR abs\/1702.05951","author":"Krauthgamer Robert","year":"2017","unstructured":"Robert Krauthgamer and Inbal Rika. 2017. Refined vertex sparsifiers of planar graphs. CoRR abs\/1702.05951 (2017). http:\/\/arxiv.org\/abs\/1702.05951"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_2_1_61_1","volume-title":"On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. CoRR abs\/1707.02190","author":"Marx D\u00e1niel","year":"2017","unstructured":"D\u00e1niel Marx, Marcin Pilipczuk, and Micha\u0142 Pilipczuk. 2017. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. CoRR abs\/1707.02190 (2017). http:\/\/arxiv.org\/abs\/1707.02190"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758778"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"e_1_2_1_64_1","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS'13)","volume":"20","author":"Pilipczuk Marcin","year":"2013","unstructured":"Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. 2013. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS'13), vol. 20, Natacha Portier and Thomas Wilke (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 353--364."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.37"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793253565"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/647903.739284"},{"key":"e_1_2_1_71_1","volume-title":"10th International Symposium on Parameterized and Exact Computation (IPEC\u201915)","volume":"43","author":"Such\u00fd Ondrej","year":"2015","unstructured":"Ondrej Such\u00fd. 2015. Extending the kernel for planar Steiner tree to the number of Steiner vertices. In 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915), September 16-18, 2015, Patras, Greece (LIPIcs), Vol. 43, Thore Husfeldt and Iyad A. Kanj (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 151--162."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.014"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3239560","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3239560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:20Z","timestamp":1750208900000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3239560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,17]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3239560"],"URL":"https:\/\/doi.org\/10.1145\/3239560","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,17]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}