{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:46Z","timestamp":1787321086555,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs [Pilipczuk et al., ACM Trans. Algorithms, 14 (2018), 53]. It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.<\/jats:p>","DOI":"10.1137\/20m1353782","type":"journal-article","created":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T13:56:50Z","timestamp":1634565410000},"page":"2387-2429","source":"Crossref","is-referenced-by-count":4,"title":["A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs"],"prefix":"10.1137","volume":"35","author":[{"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin L.","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,10,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"atypb3","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":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013,https:\/\/doi.org\/10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"atypb8","first-page":"735","author":"Eisenstat D.","year":"2013","journal-title":"ACM"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.013"},{"key":"atypb11","first-page":"470","author":"Fomin F. V.","year":"2012","journal-title":"NJ"},{"key":"atypb12","first-page":"503","author":"Fomin F. V.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/3029051"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.05.003"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"B. M. P. Jansen,\n                      Polynomial Kernels for Hard Problems on Disk Graphs\n                      , in Proceedings of the 12th SWAT, Lecture Notes in Comput. Sci. 6139, Springer, New York, 2010, pp. 310-321,https:\/\/doi.org\/10.1007\/978-3-642-13731-0_30.","DOI":"10.1007\/978-3-642-13731-0_30"},{"key":"atypb20","first-page":"1802","author":"Jansen B. M. P.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb21","first-page":"639","author":"Kawarabayashi K.","year":"2009","journal-title":"IEEE Computer Society"},{"key":"atypb22","first-page":"450","author":"Kratsch S.","year":"2012","journal-title":"IEEE Computer Society"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"atypb24","first-page":"129","author":"Lokshtanov D.","year":"2012","journal-title":"New York"},{"key":"atypb25","unstructured":"D. Lokshtanov, S. Saurabh, and M. Wahlstr\u00f6m,\n                      Subexponential parameterized odd cycle transversal on planar graphs\n                      , in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Hyderabad, D. D'Souza, T. Kavitha, and J. Radhakrishnan, eds., LIPIcs Leibniz Int. Proc. Inform. 18, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2012, pp. 424-434,https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2012.424."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"atypb27","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                      , CoRR,http:\/\/arxiv.org\/abs\/1306.6593, 2013."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"atypb29","unstructured":"I. Razgon,\n                      Large Isolating Cuts Shrink the Multiway Cut\n                      , CoRR,http:\/\/arxiv.org\/abs\/1104.5361, 2011."},{"key":"atypb30","unstructured":"S. Saurabh,\n                      Open Problems from Recent Advances in Parameterized Complexity School\n                      ,https:\/\/rapctelaviv.weebly.com\/uploads\/1\/0\/5\/3\/105379375\/future.pdf, 2017."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0249-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1353782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:20Z","timestamp":1787317580000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1353782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1353782"],"URL":"https:\/\/doi.org\/10.1137\/20m1353782","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}