{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:34Z","timestamp":1781078014938,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,3]],"date-time":"2018-01-03T00:00:00Z","timestamp":1514937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"E.U."},{"name":"Greek national funds through the Operational Program \u201cEducation and Lifelong Learning\u201d of the National Strategic Reference Framework (NSRF) - Research Funding Program: \u201cThales"},{"name":"European Research Council through ERC","award":["267959"],"award-info":[{"award-number":["267959"]}]},{"name":"Bergen Research Foundation and the University of Bergen through project \u201cBeHard\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,1,31]]},"abstract":"\n We give the first linear kernels for the D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n and C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problems on graphs excluding a fixed graph\n H<\/jats:italic>\n as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given\n H<\/jats:italic>\n -topological-minor-free\u00a0 graph\n G<\/jats:italic>\n and a positive integer\n k<\/jats:italic>\n , output an\n H<\/jats:italic>\n -topological-minor-free\u00a0 graph\n G<\/jats:italic>\n \u2032<\/jats:sup>\n on\n O<\/jats:italic>\n (\n k<\/jats:italic>\n ) vertices such that\n G<\/jats:italic>\n has a (connected) dominating set of size\n k<\/jats:italic>\n if and only if\n G<\/jats:italic>\n \u2032<\/jats:sup>\n has one.\n <\/jats:p>\n \n Our results extend the known classes of graphs on which the D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n and C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph\n H<\/jats:italic>\n as a minor. Moreover, for D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n , a kernel of size\n k<\/jats:italic>\n \n c<\/jats:italic>\n (\n H<\/jats:italic>\n )\n <\/jats:sup>\n , where\n c<\/jats:italic>\n (\n H<\/jats:italic>\n ) is a constant depending on the size of\n H<\/jats:italic>\n , follows from a more general result on the kernelization of D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on\n H<\/jats:italic>\n -minor-free\u00a0 graphs. We answer this question in the affirmative and in fact prove a more general result. For C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n no polynomial kernel even on\n H<\/jats:italic>\n -minor-free\u00a0 graphs was known prior to our work. On the negative side, it is known that C\n onnected<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n on 2-degenerated graphs does not admit a polynomial kernel unless coNP \u2286 NP\/poly.\n <\/jats:p>\n Our kernelization algorithm is based on a non-trivial combination of the following ingredients<\/jats:p>\n \n \u2022 The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph\n H<\/jats:italic>\n as a topological minor;\n <\/jats:p>\n \u2022 A novel notion of protrusions, different than the one defined in [FOCS 2009];<\/jats:p>\n \n \u2022 Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is\n H<\/jats:italic>\n -minor-free) of the problem, with treewidth\n O<\/jats:italic>\n (\u221a\n k<\/jats:italic>\n ). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels.\n <\/jats:p>\n \n A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant\n treewidth<\/jats:italic>\n , we ask that it contains a\n constant number of vertices from a solution<\/jats:italic>\n . We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.\n <\/jats:p>","DOI":"10.1145\/3155298","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors"],"prefix":"10.1145","volume":"14","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences and University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[{"name":"National and Kapodistrian University of Athens and AlGCo project-team, CNRS, LIRMM, Montpellier, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.10.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9204-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/174147.169807"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2958"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3108239"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"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":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Erik","unstructured":"Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2005. Bidimensionality: New connections between FPT algorithms and PTASs . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . ACM-SIAM, New York, NY, 590--601. Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2005. Bidimensionality: New connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). ACM-SIAM, New York, NY, 590--601."},{"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\/978-3-642-02927-1_27"},{"key":"e_1_2_1_25_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2012. Graph Theory ( 4 th ed). Graduate Texts in Mathematics, Vol. 173 . Springer . Reinhard Diestel. 2012. Graph Theory (4th ed). Graduate Texts in Mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.11.006"},{"key":"e_1_2_1_27_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1998","unstructured":"Rodney G. Downey and Michael R . Fellows . 1998 . Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 1998. Parameterized Complexity. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.10.002"},{"key":"e_1_2_1_29_1","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","volume":"47","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus Sortland Dregi , Fedor V. Fomin , Stephan Kreutzer , Daniel Lokshtanov , Marcin Pilipczuk , Michal Pilipczuk , Felix Reidl , Fernando S\u00e1nchez Villaamil , Saket Saurabh , Sebastian Siebertz , and Somnath Sikdar . 2016 . Kernelization and sparseness: The case of dominating set . In 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) , Vol. 47 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 31:1--31:14. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando S\u00e1nchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916), Vol. 47. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 31:1--31:14."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.71"},{"key":"e_1_2_1_31_1","volume-title":"Graph Theory","author":"Duchet P.","year":"1981","unstructured":"P. Duchet and H. Meyniel . 1982. On Hadwiger\u2019s number and the stability number . In Graph Theory ( Cambridge , 1981 ). North-Holland Math. Stud., Vol. 62. North-Holland, Amsterdam, 71--73. P. Duchet and H. Meyniel. 1982. On Hadwiger\u2019s number and the stability number. In Graph Theory (Cambridge, 1981). North-Holland Math. Stud., Vol. 62. North-Holland, Amsterdam, 71--73."},{"key":"e_1_2_1_32_1","volume-title":"A stronger structure theorem for excluded topological minors. CoRR abs\/1209.0129","author":"Dvorak Zdenek","year":"2012","unstructured":"Zdenek Dvorak . 2012. A stronger structure theorem for excluded topological minors. CoRR abs\/1209.0129 ( 2012 ). Zdenek Dvorak. 2012. A stronger structure theorem for excluded topological minors. CoRR abs\/1209.0129 (2012)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63528"},{"key":"e_1_2_1_36_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.02.008"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/140997889"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133095"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095240"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","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 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . ACM-SIAM, 503--510. F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). ACM-SIAM, 503--510."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Fomin F. V.","unstructured":"F. V. Fomin , D. Lokshtanov , S. Saurabh , and D. M. Thilikos . 2010. Linear kernels for (connected) dominating set on H-minor-free graphs . In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912) . ACM-SIAM, 82--93. F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2010. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). ACM-SIAM, 82--93."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","volume":"20","author":"Fomin Fedor V.","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M. Thilikos . 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs . In Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) , Vol. 20 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 92--103. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913), Vol. 20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 92--103."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419649"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92248-3_18"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/120892234"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_20"},{"key":"e_1_2_1_49_1","volume-title":"Slater","author":"Haynes Teresa W.","year":"1998","unstructured":"Teresa W. Haynes , Stephen T. Hedetniemi , and Peter J . Slater . 1998 . Fundamentals of Domination in Graphs. Marcel Dekker Inc ., New York, NY. Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York, NY."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908)","volume":"5035","author":"Yusuke Kobayashi Kawarabayashi","year":"2008","unstructured":"Ken-ichi Kawarabayashi and Yusuke Kobayashi . 2008 . The induced disjoint path problem . In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908) . Lecture Notes in Computer Science , Vol. 5035 . Springer, Berlin, 47--61. Ken-ichi Kawarabayashi and Yusuke Kobayashi. 2008. The induced disjoint path problem. In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908). Lecture Notes in Computer Science, Vol. 5035. Springer, Berlin, 47--61."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806785"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496894"},{"key":"e_1_2_1_55_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 , Oxford . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390187"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_51"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155298","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3155298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:28Z","timestamp":1750213588000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3155298"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,3]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3155298"],"URL":"https:\/\/doi.org\/10.1145\/3155298","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,3]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}