{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T06:54:49Z","timestamp":1770447289034,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T00:00:00Z","timestamp":1489968000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"\u201cParameterized Approximation.\u201d"},{"name":"NWO Veni grant \u201cFrontiers in Parameterized Preprocessing\u201d and the NWO Gravitation grant \u201cNetworks.\u201d"},{"name":"Bergen Research Foundation grant BeHard"},{"name":"ERC","award":["267959 and 306992"],"award-info":[{"award-number":["267959 and 306992"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>F<\/jats:italic>\n            -M\n            <jats:sc>inor<\/jats:sc>\n            -F\n            <jats:sc>ree<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            problem asks, for a fixed set\n            <jats:italic>F<\/jats:italic>\n            and an input consisting of a graph\n            <jats:italic>G<\/jats:italic>\n            and integer\n            <jats:italic>k<\/jats:italic>\n            , whether\n            <jats:italic>k<\/jats:italic>\n            vertices can be removed from\n            <jats:italic>G<\/jats:italic>\n            such that the resulting graph does not contain any member of\n            <jats:italic>F<\/jats:italic>\n            as a minor. At FOCS 2012, Fomin et al. showed that the special case when\n            <jats:italic>F<\/jats:italic>\n            contains at least one planar graph has a kernel of size\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) \u010b\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>g<\/jats:italic>\n              (\n              <jats:italic>F<\/jats:italic>\n              )\n            <\/jats:sup>\n            for some functions\n            <jats:italic>f<\/jats:italic>\n            and\n            <jats:italic>g<\/jats:italic>\n            . They left open whether this P\n            <jats:sc>lanar<\/jats:sc>\n            <jats:italic>F<\/jats:italic>\n            -M\n            <jats:sc>inor<\/jats:sc>\n            -F\n            <jats:sc>ree<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            problem has kernels whose size is uniformly polynomial, of the form\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>F<\/jats:italic>\n            ) \u010b\n            <jats:italic>\n              k\n              <jats:sup>c<\/jats:sup>\n            <\/jats:italic>\n            for some universal constant\n            <jats:italic>c<\/jats:italic>\n            . We prove that some P\n            <jats:sc>lanar<\/jats:sc>\n            <jats:italic>F<\/jats:italic>\n            -M\n            <jats:sc>inor<\/jats:sc>\n            -F\n            <jats:sc>ree<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            problems do not have uniformly polynomial kernels (unless NP \u2286 coNP\/poly), not even when parameterized by the vertex cover number. On the positive side, we consider the problem of determining whether\n            <jats:italic>k<\/jats:italic>\n            vertices can be removed to obtain a graph of treedepth at most \u03b7. We prove that this problem admits uniformly polynomial kernels with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>6<\/jats:sup>\n            ) vertices for every fixed \u03b7.\n          <\/jats:p>","DOI":"10.1145\/3029051","type":"journal-article","created":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T12:18:59Z","timestamp":1490098739000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Uniform Kernelization Complexity of Hitting Forbidden Minors"],"prefix":"10.1145","volume":"13","author":[{"given":"Archontia C.","family":"Giannopoulou","sequence":"first","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8204-1268","authenticated-orcid":false,"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, MB Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","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 (SODA\u201908) . 641--650. Isolde Adler, Martin Grohe, and Stephan Kreutzer. 2008. Computing excluded minors. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 641--650."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9428-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_31"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/120903518"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591813"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1992260302571"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_13"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635820"},{"key":"e_1_2_1_16_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag New York NY.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag New York NY."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.09.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997889"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873644"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_45"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_51"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_48"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9559-5"},{"key":"e_1_2_1_28_1","first-page":"58","article-title":"Recent developments in kernelization: A survey","volume":"113","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014 . Recent developments in kernelization: A survey . Bulletin of EATCS 113 , 58 -- 97 . Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bulletin of EATCS 113, 58--97.","journal-title":"Bulletin of EATCS"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2344236.2344248"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.37"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_39_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . 2003 . Combinatorial Optimization: Polyhedra and Efficiency . Springer, Berlin , Germany . Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin, Germany."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3029051","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3029051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:15Z","timestamp":1750220595000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3029051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,20]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3029051"],"URL":"https:\/\/doi.org\/10.1145\/3029051","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,20]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}