{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:17:27Z","timestamp":1770279447332,"version":"3.49.0"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T00:00:00Z","timestamp":1449532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Theoretical and Practical Aspects of Kernelization"},{"name":"Languedoc-Roussillon Project \u201cChercheur d'avenir\u201d KERNEL"},{"name":"DFG-Project RO","award":["927\/12-1"],"award-info":[{"award-number":["927\/12-1"]}]},{"name":"ANR project AGAPE","award":["ANR-09-BLAN-0159"],"award-info":[{"award-number":["ANR-09-BLAN-0159"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            We present a linear-time algorithm to compute a decomposition scheme for graphs\n            <jats:italic>G<\/jats:italic>\n            that have a set\n            <jats:italic>X<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ), called a\n            <jats:italic>treewidth-modulator<\/jats:italic>\n            , such that the treewidth of\n            <jats:italic>G<\/jats:italic>\n            \u2212\n            <jats:italic>X<\/jats:italic>\n            is bounded by a constant. Our decomposition, called a\n            <jats:italic>protrusion decomposition<\/jats:italic>\n            , is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter\n            <jats:italic>k<\/jats:italic>\n            ) that has a\n            <jats:italic>finite integer index<\/jats:italic>\n            and such that Y\n            <jats:sc>es<\/jats:sc>\n            -instances have a treewidth-modulator of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) admits a linear kernel on the class of\n            <jats:italic>H<\/jats:italic>\n            -topological-minor-free graphs, for any fixed graph\n            <jats:italic>H<\/jats:italic>\n            . This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and\n            <jats:italic>H<\/jats:italic>\n            -minor-free graphs. Let\n            <jats:italic>F<\/jats:italic>\n            be a fixed finite family of graphs containing at least one planar graph. Given an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            and a non-negative integer\n            <jats:italic>k<\/jats:italic>\n            , P\n            <jats:sc>lanar<\/jats:sc>\n            -\n            <jats:italic>F<\/jats:italic>\n            -D\n            <jats:sc>eletion<\/jats:sc>\n            asks whether\n            <jats:italic>G<\/jats:italic>\n            has a set\n            <jats:italic>X<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) such that |\n            <jats:italic>X<\/jats:italic>\n            | \u2a7d\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>G<\/jats:italic>\n            \u2212\n            <jats:italic>X<\/jats:italic>\n            is\n            <jats:italic>H<\/jats:italic>\n            -minor-free for every\n            <jats:italic>H<\/jats:italic>\n            \u03f5\n            <jats:italic>F<\/jats:italic>\n            . As our second application, we present the first\n            <jats:italic>single-exponential<\/jats:italic>\n            algorithm to solve P\n            <jats:sc>lanar<\/jats:sc>\n            -\n            <jats:italic>F<\/jats:italic>\n            -D\n            <jats:sc>eletion<\/jats:sc>\n            . Namely, our algorithm runs in time 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u00b7\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            , which is asymptotically optimal with respect to\n            <jats:italic>k<\/jats:italic>\n            . So far, single-exponential algorithms were only known for special cases of the family\n            <jats:italic>F<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2797140","type":"journal-article","created":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T14:22:10Z","timestamp":1449757330000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions"],"prefix":"10.1145","volume":"12","author":[{"given":"Eun Jung","family":"Kim","sequence":"first","affiliation":[{"name":"CNRS LAMSADE Paris"}]},{"given":"Alexander","family":"Langer","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[{"name":"CNRS LIRMM Montpellier"}]},{"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[{"name":"CNRS LIRMM Montpellier"}]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2015,12,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of Graph Structure Theory, Contemporary Mathematics 147","author":"Abrahamson K. R.","unstructured":"K. R. Abrahamson and M. R. Fellows . 1991. Finite automata, bounded treewidth, and well-quasiordering . In Proceedings of Graph Structure Theory, Contemporary Mathematics 147 . American Mathematical Society, 539--564. K. R. Abrahamson and M. R. Fellows. 1991. Finite automata, bounded treewidth, and well-quasiordering. In Proceedings of Graph Structure Theory, Contemporary Mathematics 147. American Mathematical Society, 539--564."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169807"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10847-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646242.681417"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd IWPEC (LNCS). Springer, 160--171","author":"Bodlaender H. L.","unstructured":"H. L. Bodlaender and E. Penninkx . 2008. A linear kernel for planar feedback vertex set . In Proceedings of the 3rd IWPEC (LNCS). Springer, 160--171 . H. L. Bodlaender and E. Penninkx. 2008. A linear kernel for planar feedback vertex set. In Proceedings of the 3rd IWPEC (LNCS). Springer, 160--171."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_29"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 17th ESA (LNCS). Springer, 635--646","author":"Bodlaender H. L.","unstructured":"H. L. Bodlaender , S. Thomass\u00e9 , and A. Yeo . 2009. Kernel bounds for disjoint cycles and disjoint paths . In Proceedings of the 17th ESA (LNCS). Springer, 635--646 . H. L. Bodlaender, S. Thomass\u00e9, and A. Yeo. 2009. Kernel bounds for disjoint cycles and disjoint paths. In Proceedings of the 17th ESA (LNCS). Springer, 635--646."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2958"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/307654.307655"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Congress on Logic, Methodology, and Philosophy of Science. 1--11","author":"B\u00fcchi J. R.","year":"1962","unstructured":"J. R. B\u00fcchi . 1962 . On a decision method in restricted second-order arithmetic . In Proceedings of the International Congress on Logic, Methodology, and Philosophy of Science. 1--11 . J. R. B\u00fcchi. 1962. On a decision method in restricted second-order arithmetic. In Proceedings of the International Congress on Logic, Methodology, and Philosophy of Science. 1--11."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_17_1","volume-title":"Linear recognition of almost interval graphs. CoRR abs\/1403.1515","author":"Cao Y.","year":"2014","unstructured":"Y. Cao . 2014. Linear recognition of almost interval graphs. CoRR abs\/1403.1515 ( 2014 ). Y. Cao. 2014. Linear recognition of almost interval graphs. CoRR abs\/1403.1515 (2014)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629595"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"B. Courcelle and J. Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach. Number 138 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press.   B. Courcelle and J. Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach. Number 138 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511977619"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 5th IWPEC (LNCS). Springer, 95--106","author":"Cygan M.","unstructured":"M. Cygan , M. Pilipczuk , M. Pilipczuk , and J. Wojtaszczyk . 2010. An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion . In Proceedings of the 5th IWPEC (LNCS). Springer, 95--106 . M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. Wojtaszczyk. 2010. An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion. In Proceedings of the 5th IWPEC (LNCS). Springer, 95--106."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 11th COCOON (LNCS). Springer, 859--869","author":"Dehne F. K. H. A.","unstructured":"F. K. H. A. Dehne , M. R. Fellows , M. A. Langston , F. A. Rosamond , and K. Stevens . 2005. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem . In Proceedings of the 11th COCOON (LNCS). Springer, 859--869 . F. K. H. A. Dehne, M. R. Fellows, M. A. Langston, F. A. Rosamond, and K. Stevens. 2005. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of the 11th COCOON (LNCS). Springer, 859--869."},{"key":"e_1_2_1_28_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2010. Graph Theory ( 4 th ed.). Springer-Verlag , Heidelberg . R. Diestel. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg.","edition":"4"},{"key":"e_1_2_1_29_1","first-page":"1199","article-title":"Too many minor order obstructions","volume":"3","author":"Dinneen M. J.","year":"1997","unstructured":"M. J. Dinneen . 1997 . Too many minor order obstructions . Journal of Universal Computer Science 3 , 11 (1997), 1199 -- 1206 . M. J. Dinneen. 1997. Too many minor order obstructions. Journal of Universal Computer Science 3, 11 (1997), 1199--1206.","journal-title":"Journal of Universal Computer Science"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 19th SODA. SIAM, 631--640","author":"Dorn F.","unstructured":"F. Dorn , F. V. Fomin , and D. M. Thilikos . 2008. Catalan structures and dynamic programming in H-minor-free graphs . In Proceedings of the 19th SODA. SIAM, 631--640 . F. Dorn, F. V. Fomin, and D. M. Thilikos. 2008. Catalan structures and dynamic programming in H-minor-free graphs. In Proceedings of the 19th SODA. SIAM, 631--640."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer-Verlag.   R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44491"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63528"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80079-0"},{"key":"e_1_2_1_36_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 30th STACS (LIPIcs)","volume":"20","author":"Fomin F.","unstructured":"F. Fomin , D. Lokshtanov , S. Saurabh , and D. M. Thilikos . 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs . In Proceedings of the 30th STACS (LIPIcs) , Vol. 20 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 92--103. F. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In Proceedings of the 30th STACS (LIPIcs), Vol. 20. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 92--103."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_11"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 28th STACS (LIPIcs)","volume":"9","author":"Fomin F. V.","unstructured":"F. V. Fomin , D. Lokshtanov , N. Misra , G. Philip , and S. Saurabh . 2011. Hitting forbidden minors: Approximation and kernelization . In Proceedings of the 28th STACS (LIPIcs) , Vol. 9 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 189--200. F. V. Fomin, D. Lokshtanov, N. Misra, G. Philip, and S. Saurabh. 2011. Hitting forbidden minors: Approximation and kernelization. In Proceedings of the 28th STACS (LIPIcs), Vol. 9. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 189--200."},{"key":"e_1_2_1_40_1","unstructured":"F. V. Fomin D. Lokshtanov N. Misra and S. Saurabh. 2011. Nearly optimal FPT algorithms for Planar-F-Deletion. (2011). Unpublished manuscript.  F. V. Fomin D. Lokshtanov N. Misra and S. Saurabh. 2011. Nearly optimal FPT algorithms for Planar- F -Deletion. (2011). Unpublished manuscript."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_42_1","unstructured":"F. V. Fomin D. Lokshtanov N. Misra and S. Saurabh. 2012b. Planar-F Deletion: Kernelization and obstruction bounds. (2012). Unpublished manuscript.  F. V. Fomin D. Lokshtanov N. Misra and S. Saurabh. 2012b. Planar- F Deletion: Kernelization and obstruction bounds. (2012). Unpublished manuscript."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 21st SODA. SIAM, 503--510","author":"Fomin F. V.","unstructured":"F. V. Fomin , D. Lokshtanov , S. Saurabh , and D. M. Thilikos . 2010. Bidimensionality and kernels . In Proceedings of the 21st SODA. SIAM, 503--510 . F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st SODA. SIAM, 503--510."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 23rd SODA. SIAM, 82--93","author":"Fomin F. V.","unstructured":"F. V. Fomin , D. Lokshtanov , S. Saurabh , and D. M. Thilikos . 2012. Linear kernels for (connected) dominating set on H-minor-free graphs . In Proceedings of the 23rd SODA. SIAM, 82--93 . F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2012. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the 23rd SODA. SIAM, 82--93."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.05.003"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 21st ESA (LNCS). Springer, 529--540","author":"Gajarsk\u00fd J.","unstructured":"J. Gajarsk\u00fd , P. Hlinen\u00fd , J. Obdrz\u00e1lek , S. Ordyniak , F. Reidl , P. Rossmanith , F. S\u00e1nchez Villaamil , and S. Sikdar . 2013. Kernelization using structural parameters on sparse graph classes . In Proceedings of the 21st ESA (LNCS). Springer, 529--540 . J. Gajarsk\u00fd, P. Hlinen\u00fd, J. Obdrz\u00e1lek, S. Ordyniak, F. Reidl, P. Rossmanith, F. S\u00e1nchez Villaamil, and S. Sikdar. 2013. Kernelization using structural parameters on sparse graph classes. In Proceedings of the 21st ESA (LNCS). Springer, 529--540."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 38th MFCS (LNCS). Springer, 457--468","author":"Ganian R.","unstructured":"R. Ganian , F. Slivovsky , and S. Szeider . 2013. Meta-kernelization with structural parameters . In Proceedings of the 38th MFCS (LNCS). Springer, 457--468 . R. Ganian, F. Slivovsky, and S. Szeider. 2013. Meta-kernelization with structural parameters. In Proceedings of the 38th MFCS (LNCS). Springer, 457--468."},{"key":"e_1_2_1_49_1","unstructured":"M. Grohe and D. Marx. 2011. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. CoRR abs\/1111.1109 (2011).  M. Grohe and D. Marx. 2011. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. CoRR abs\/1111.1109 (2011)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 34th ICALP (LNCS). Springer, 375--386","author":"Guo J.","unstructured":"J. Guo and R. Niedermeier . 2007. Linear problem kernels for NP-hard problems on planar graphs . In Proceedings of the 34th ICALP (LNCS). Springer, 375--386 . J. Guo and R. Niedermeier. 2007. Linear problem kernels for NP-hard problems on planar graphs. In Proceedings of the 34th ICALP (LNCS). Springer, 375--386."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v56:2"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 25th SODA. SIAM","author":"Jansen B. M. P.","unstructured":"B. M. P. Jansen , D. Lokshtanov , and S. Saurabh . 2014. A near-optimal planarization algorithm . In Proceedings of the 25th SODA. SIAM , 1802--1811. B. M. P. Jansen, D. Lokshtanov, and S. Saurabh. 2014. A near-optimal planarization algorithm. In Proceedings of the 25th SODA. SIAM, 1802--1811."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 19th ESA (LNCS). Springer, 394--407","author":"Joret G.","unstructured":"G. Joret , C. Paul , I. Sau , S. Saurabh , and S. Thomass\u00e9 . 2011. Hitting and harvesting pumpkins . In Proceedings of the 19th ESA (LNCS). Springer, 394--407 . G. Joret, C. Paul, I. Sau, S. Saurabh, and S. Thomass\u00e9. 2011. Hitting and harvesting pumpkins. In Proceedings of the 19th ESA (LNCS). Springer, 394--407."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.09.001"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.45"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_11"},{"key":"e_1_2_1_58_1","volume-title":"Number 842 in LNCS","author":"Kloks T.","unstructured":"T. Kloks . 1994. Treewidth, Computations and Approximations . Number 842 in LNCS . Springer . T. Kloks. 1994. Treewidth, Computations and Approximations. Number 842 in LNCS. Springer."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"e_1_2_1_60_1","first-page":"147","article-title":"Algorithmic meta-theorems","volume":"16","author":"Kreutzer S.","year":"2009","unstructured":"S. Kreutzer . 2009 . Algorithmic meta-theorems . Electronic Colloquium on Computational Complexity 16 (2009), 147 . S. Kreutzer. 2009. Algorithmic meta-theorems. Electronic Colloquium on Computational Complexity 16 (2009), 147.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of 21st SODA. SIAM, 354--364","author":"Kreutzer S.","unstructured":"S. Kreutzer and S. Tazari . 2010. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic . In Proceedings of 21st SODA. SIAM, 354--364 . S. Kreutzer and S. Tazari. 2010. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic. In Proceedings of 21st SODA. SIAM, 354--364."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789708"},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of 22nd SODA. SIAM, 760--776","author":"Lokshtanov D.","unstructured":"D. Lokshtanov , D. Marx , and S. Saurabh . 2011a. Slightly superexponential parameterized problems . In Proceedings of 22nd SODA. SIAM, 760--776 . D. Lokshtanov, D. Marx, and S. Saurabh. 2011a. Slightly superexponential parameterized problems. In Proceedings of 22nd SODA. SIAM, 760--776."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.045"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9484-z"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90170-2"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.011"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0135681-9"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_73_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","unstructured":"R. Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . R. Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 36th WG (LNCS). Springer, 196--207","author":"Philip G.","unstructured":"G. Philip , V. Raman , and Y. Villanger . 2010. A quartic kernel for pathwidth-one vertex deletion . In Proceedings of the 36th WG (LNCS). Springer, 196--207 . G. Philip, V. Raman, and Y. Villanger. 2010. A quartic kernel for pathwidth-one vertex deletion. In Proceedings of the 36th WG (LNCS). Springer, 196--207."},{"key":"e_1_2_1_76_1","volume-title":"Single exponential FPT algorithm for interval vertex deletion and interval completion problem. CoRR abs\/1211.4629","author":"Rafiey Arash","year":"2012","unstructured":"Arash Rafiey . 2012. Single exponential FPT algorithm for interval vertex deletion and interval completion problem. CoRR abs\/1211.4629 ( 2012 ). Arash Rafiey. 2012. Single exponential FPT algorithm for interval vertex deletion and interval completion problem. CoRR abs\/1211.4629 (2012)."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_1_83_1","unstructured":"J. Ru\u00e9 I. Sau and D. M. Thilikos. 2011. Dynamic programming for graphs on surfaces. CoRR abs\/1104.2486 (2011). To appear in ACM Transactions on Algorithms.  J. Ru\u00e9 I. Sau and D. M. Thilikos. 2011. Dynamic programming for graphs on surfaces. CoRR abs\/1104.2486 (2011). To appear in ACM Transactions on Algorithms."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9977-x"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1137\/0138030"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2797140","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2797140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:29Z","timestamp":1750225409000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2797140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,8]]},"references-count":85,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2797140"],"URL":"https:\/\/doi.org\/10.1145\/2797140","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,8]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}