{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T16:21:55Z","timestamp":1784046115741,"version":"3.55.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,12]]},"abstract":"\n We show that for every fixed\n j<\/jats:italic>\n \u2265\n i<\/jats:italic>\n \u2265 1, the\n k<\/jats:italic>\n -D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problem restricted to graphs that do not have\n \n K\n ij<\/jats:sub>\n <\/jats:italic>\n (the complete bipartite graph on (\n i<\/jats:italic>\n +\n j<\/jats:italic>\n ) vertices, where the two parts have\n i<\/jats:italic>\n and\n j<\/jats:italic>\n vertices, respectively) as a subgraph is fixed parameter tractable (FPT) and has a polynomial kernel. We describe a polynomial-time algorithm that, given a\n \n K\n i,j<\/jats:sub>\n <\/jats:italic>\n -free graph\n G<\/jats:italic>\n and a nonnegative integer\n k<\/jats:italic>\n , constructs a graph\n H<\/jats:italic>\n (the \u201ckernel\u201d) and an integer\n k<\/jats:italic>\n ' such that (1)\n G<\/jats:italic>\n has a dominating set of size at most\n k<\/jats:italic>\n if and only if\n H<\/jats:italic>\n has a dominating set of size at most\n k<\/jats:italic>\n ', (2)\n H<\/jats:italic>\n has\n O<\/jats:italic>\n ((\n j<\/jats:italic>\n + 1)\n \n i<\/jats:italic>\n + 1\n <\/jats:sup>\n \n k\n i<\/jats:sup>\n 2<\/jats:sup>\n <\/jats:italic>\n ) vertices, and (3)\n k<\/jats:italic>\n ' =\n O<\/jats:italic>\n ((\n j<\/jats:italic>\n + 1)\n \n i<\/jats:italic>\n + 1\n <\/jats:sup>\n \n k\n i<\/jats:sup>\n 2<\/jats:sup>\n <\/jats:italic>\n ).\n <\/jats:p>\n \n Since\n d<\/jats:italic>\n -degenerate graphs do not have\n \n K\n d+1,d+1<\/jats:sub>\n <\/jats:italic>\n as a subgraph, this immediately yields a polynomial kernel on\n O<\/jats:italic>\n ((\n d<\/jats:italic>\n + 2)\n \n d<\/jats:italic>\n +2\n <\/jats:sup>\n k<\/jats:italic>\n \n (\n d<\/jats:italic>\n + 1)\n <\/jats:sup>\n 2<\/jats:sup>\n ) vertices for the\n k<\/jats:italic>\n -D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problem on\n d<\/jats:italic>\n -degenerate graphs, solving an open problem posed by Alon and Gutner [Alon and Gutner 2008; Gutner 2009].\n <\/jats:p>\n \n The most general class of graphs for which a polynomial kernel was previously known for\n k<\/jats:italic>\n -D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n is the class of\n \n K\n h<\/jats:sub>\n <\/jats:italic>\n -topological-minor-free graphs [Gutner 2009]. Graphs of bounded degeneracy are the most general class of graphs for which an FPT algorithm was previously known for this problem.\n \n K\n h<\/jats:sub>\n <\/jats:italic>\n -topological-minor-free graphs are\n \n K\n i,j<\/jats:sub>\n <\/jats:italic>\n -free for suitable values of\n i,j<\/jats:italic>\n (but not vice-versa), and so our results show that\n k<\/jats:italic>\n -D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n has both FPT algorithms and polynomial kernels in strictly more general classes of graphs.\n <\/jats:p>\n \n Using the same techniques, we also obtain an\n O<\/jats:italic>\n (\n \n jk\n i<\/jats:sup>\n <\/jats:italic>\n ) vertex-kernel for the\n k<\/jats:italic>\n -I\n ndependent<\/jats:sc>\n D\n ominating<\/jats:sc>\n S\n et<\/jats:sc>\n problem on\n \n K\n i,j<\/jats:sub>\n <\/jats:italic>\n -free graphs.\n <\/jats:p>","DOI":"10.1145\/2390176.2390187","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond"],"prefix":"10.1145","volume":"9","author":[{"given":"Geevarghese","family":"Philip","sequence":"first","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Somnath","family":"Sikdar","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,12,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_2_1","volume-title":"Tech. Rep. TR08-066, The Electronic Colloquium on Computational Complexity (ECCC).","author":"Alon N.","year":"2008","unstructured":"Alon , N. and Gutner , S . 2008 . Kernels for the dominating set problem on graphs with an excluded minor. Tech. Rep. TR08-066, The Electronic Colloquium on Computational Complexity (ECCC). Alon, N. and Gutner, S. 2008. Kernels for the dominating set problem on graphs with an excluded minor. Tech. Rep. TR08-066, The Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9204-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1906"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.10.020"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_8_1","volume-title":"Extremal graph theory","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. 2004. Extremal graph theory . Dover Publications . Bollob\u00e1s, B. 2004. Extremal graph theory. Dover Publications."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/307654.307655"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1939238.1939255"},{"key":"e_1_2_1_12_1","unstructured":"Dawar A. and Kreutzer S. 2009. Domination problems in nowhere-dense classes. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009). R. Kannan and K. N. Kumar Eds. Leibniz International Proceedings in Informatics (LIPIcs) Series vol. 4 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Dagstuhl Germany 157--168. Dawar A. and Kreutzer S. 2009. Domination problems in nowhere-dense classes. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009). R. Kannan and K. N. Kumar Eds. Leibniz International Proceedings in Informatics (LIPIcs) Series vol. 4 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Dagstuhl Germany 157--168."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"e_1_2_1_15_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"Diestel , R. 2005. Graph Theory 3 rd Ed. Springer-Verlag , Berlin . Diestel, R. 2005. Graph Theory 3rd Ed. Springer-Verlag, Berlin.","edition":"3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321781"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.001"},{"key":"e_1_2_1_20_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer-Verlag. Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer-Verlag."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Fomin F. V.","year":"2010","unstructured":"Fomin , F. V. , Lokshtanov , D. , Saurabh , S. , and Thilikos , D. M . 2010. Bidimensionality and kernels . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010 ). SIAM, 503--510. Fomin, F. V., Lokshtanov, D., Saurabh, S., and Thilikos, D. M. 2010. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). SIAM, 503--510."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_50"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419649"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.12.008"},{"key":"e_1_2_1_25_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP--Completeness. Freeman San Francisco. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP--Completeness. Freeman San Francisco."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92248-3_18"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_20"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Habib M. Paul C. and \n Viennot L\n . \n 1998\n . A synthesis on partition refinement: A useful routine for strings graphs Boolean matrices and automata. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 98). M. Morvan C. Meinel and D. Krob Eds. Lecture Notes in Computer Science Series vol. \n 1373 Springer 25--38. Habib M. Paul C. and Viennot L. 1998. A synthesis on partition refinement: A useful routine for strings graphs Boolean matrices and automata. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 98). M. Morvan C. Meinel and D. Krob Eds. Lecture Notes in Computer Science Series vol. 1373 Springer 25--38.","DOI":"10.1007\/BFb0028546"},{"key":"e_1_2_1_30_1","series-title":"Pure and applied mathematics: A series of monographs and textbooks series","volume-title":"Graphs: Advanced topics","author":"Haynes T. W.","year":"1998","unstructured":"Haynes , T. W. , Hedetniemi , S. T. , and Slater , P. J . 1998 a. Domination in Graphs: Advanced topics . Pure and applied mathematics: A series of monographs and textbooks series , vol. 209 , Marcel Dekker , Inc. Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. 1998a. Domination in Graphs: Advanced topics. Pure and applied mathematics: A series of monographs and textbooks series, vol. 209, Marcel Dekker, Inc."},{"key":"e_1_2_1_31_1","unstructured":"Haynes T. W. Hedetniemi S. T. and Slater P. J. 1998b. Fundamentals of Domination in Graphs. Pure and applied mathematics: A series of monographs and textbooks series vol. 208 Marcel Dekker Inc. Haynes T. W. Hedetniemi S. T. and Slater P. J. 1998b. Fundamentals of Domination in Graphs. Pure and applied mathematics: A series of monographs and textbooks series vol. 208 Marcel Dekker Inc."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"e_1_2_1_33_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 17th Annual European Symposium on Algorithms (ESA","volume":"5757","author":"Philip G.","year":"2009","unstructured":"Philip , G. , Raman , V. , and Sikdar , S . 2009. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels . In Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009 ). Lecture Notes in Computer Science Series , vol. 5757 , Springer, 694--705. Philip, G., Raman, V., and Sikdar, S. 2009. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009). Lecture Notes in Computer Science Series, vol. 5757, Springer, 694--705."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9148-9"},{"key":"e_1_2_1_36_1","first-page":"423","article-title":"Regular graphs with given girth and restricted circuits. J. London","volume":"1","author":"Sachs H.","year":"1963","unstructured":"Sachs , H. 1963 . Regular graphs with given girth and restricted circuits. J. London Math. Soc. s1-38 , 1 , 423 -- 429 . Sachs, H. 1963. Regular graphs with given girth and restricted circuits. J. London Math. Soc. s1-38, 1, 423--429.","journal-title":"Math. Soc. s1-38"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390187","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2390176.2390187","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:45Z","timestamp":1750235745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390187"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2390176.2390187"],"URL":"https:\/\/doi.org\/10.1145\/2390176.2390187","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}