{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:40Z","timestamp":1781078020798,"version":"3.54.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T00:00:00Z","timestamp":1683244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Council of Norway via the project BWCA","award":["314528"],"award-info":[{"award-number":["314528"]}]},{"name":"ANR projects DEMOGRAPH","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}]},{"name":"ESIGMA","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]},{"name":"French-German Collaboration ANR\/DFG Project UTMA","award":["ANR-20-CE92-0027"],"award-info":[{"award-number":["ANR-20-CE92-0027"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            For a finite collection of graphs \u2131, the \u2131-\n            <jats:sc>TM-Deletion<\/jats:sc>\n            problem has as input an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            and asks whether there exists a set\n            <jats:italic>S \u2286 V(G)<\/jats:italic>\n            with\n            <jats:italic>|S| \u2264 k<\/jats:italic>\n            such that\n            <jats:italic>G \\ S<\/jats:italic>\n            does not contain any of the graphs in \u2131 as a topological minor. We prove that for every such \u2131, \u2131 -\n            <jats:sc>TM-Deletion<\/jats:sc>\n            is fixed parameter tractable on planar graphs. Our algorithm runs in a 2\n            <jats:sup>\n              \ud835\udcaa(\n              <jats:italic>k<\/jats:italic>\n              2)\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            time, or, alternatively, in 2\n            <jats:sup>\n              \ud835\udcaa(\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.\n          <\/jats:p>","DOI":"10.1145\/3583688","type":"journal-article","created":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T12:41:14Z","timestamp":1676032874000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4175-7793","authenticated-orcid":false,"given":"Giannos","family":"Stamoulis","sequence":"additional","affiliation":[{"name":"LIRMM, Univ Montpellier, CNRS, Montpellier, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0470-1800","authenticated-orcid":false,"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[{"name":"LIRMM, Univ Montpellier, CNRS, Montpellier, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,5]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.015"},{"key":"e_1_3_2_3_2","first-page":"641","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Adler Isolde","year":"2008","unstructured":"Isolde Adler, Martin Grohe, and Stephan Kreutzer. 2008. Computing excluded minors. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 641\u2013650. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347153."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.10.001"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_7_2","unstructured":"Julien Baste Ignasi Sau and Dimitrios M. Thilikos. 2019. Hitting minors on bounded treewidth graphs. IV. An optimal algorithm. arXiv:1907.04442. Retrieved from https:\/\/arxiv.org\/abs\/1907.04442."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1287146"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.4.2.38"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110111"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/120864271"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i1a7"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.29"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2140-4"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28629-5_12"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190507"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.02.008"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384318"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080264"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.26"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2003.07.007"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/141000014"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.56"},{"key":"e_1_3_2_32_2","unstructured":"Petr A. Golovach Giannos Stamoulis and Dimitrios M. Thilikos. 2022. Combing a Linkage in an Annulus. arXiv:2207.04798. Retrieved from https:\/\/arxiv.org\/abs\/2207.04798."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.041"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993700"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9627-5"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.130"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2012.182"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.004"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374443"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.53"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806785"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"e_1_3_2_46_2","unstructured":"Fr\u00e9d\u00e9ric Mazoit. 2013. A single exponential bound for the redundant vertex Theorem on surfaces. arXiv:1309.7820. Retrieved from https:\/\/arxiv.org\/abs\/1309.7820."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519028"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583688","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:28Z","timestamp":1750178788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,5]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3583688"],"URL":"https:\/\/doi.org\/10.1145\/3583688","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,5]]},"assertion":[{"value":"2021-11-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}