{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:19Z","timestamp":1787322859325,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Defense Service Organization"},{"name":"Chennai Mathematical Institute"},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["R-252-000-B14-281"],"award-info":[{"award-number":["R-252-000-B14-281"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["VRG18012"],"award-info":[{"award-number":["VRG18012"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA01\/2017-18"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For a positive integer [Formula: see text], a graph [Formula: see text] is said to be [Formula: see text]-closed if every pair of nonadjacent vertices in [Formula: see text] have at most [Formula: see text] neighbors in common. The closure of a graph [Formula: see text], denoted by [Formula: see text], is the least positive integer [Formula: see text] for which [Formula: see text] is [Formula: see text]-closed. The class of [Formula: see text]-closed graphs was introduced by J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein [Proceedings of the International Colloquium on Automata, Languages, and Programming (2018), 55; SIAM J. Comput., 49 (2020), pp. 448\u2013464]. T. Koana, C. Komusiewicz, and F. Sommer [Proceedings of the European Symposium on Algorithms (2020), 65; SIAM J. Discrete Math., 36 (2022), pp. 2798\u20132821] started the study of using [Formula: see text] as an additional structural parameter to design kernels for problems that are W -hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set, and (Threshold) Dominating Set and showed that each of these problems admits a polynomial kernel when parameterized either by [Formula: see text] or by [Formula: see text] for each fixed value of [Formula: see text]. Here, [Formula: see text] is the solution size and [Formula: see text]. The work of Koana et\u00a0al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable ( FPT ) algorithm and a polynomial kernel on [Formula: see text]-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable when parameterized by [Formula: see text], whereas Partial Dominating Set, parameterized by [Formula: see text] is [Formula: see text]-hard even when [Formula: see text]. We also show that for each fixed [Formula: see text], Perfect Code admits a polynomial kernel on the class of [Formula: see text]-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs unless NP [Formula: see text] co- NP \/poly.<\/jats:p>","DOI":"10.1137\/22m1491721","type":"journal-article","created":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T18:02:08Z","timestamp":1699639328000},"page":"2626-2669","source":"Crossref","is-referenced-by-count":2,"title":["Further Exploiting\n                    <i>c<\/i>\n                    -Closure for FPT Algorithms and Kernels for Domination Problems"],"prefix":"10.1137","volume":"37","author":[{"given":"Lawqueen","family":"Kanesh","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jayakrishnan","family":"Madathil","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjukta","family":"Roy","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, State College, PA 16801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Sahu","sequence":"additional","affiliation":[{"name":"National Institute of Science Education and Research, HBNI, Bhubaneswar, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India, and University of Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,11,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0116-5"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.03.007"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9204-0"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.12.002"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.05.015"},{"key":"ref6","unstructured":"B. Behera, E. Husic, S. Jain, T. Roughgarden, and C. Seshadhri, FPT algorithms for finding near-cliques in c-closed graphs, in 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31\u2013February 3, 2022, Berkeley, CA, USA, LIPIcs. Leibniz Int. Proc. Inform. 215, M. Braverman, ed. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2022, 17, https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.17."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00434-9"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90078-9"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm086"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"L. Cai, S. M. Chan, and S. O. Chan, Random separation: A new method for solving fixed-cardinality optimization problems, in Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13\u201315, 2006, Proceedings, Lecture Notes in Comput. Sci. 4169, H. L. Bodlaender and M. A. Langston, eds. Springer, Berlin, 2006, pp. 239\u2013250, https:\/\/doi.org\/10.1007\/11847250_22.","DOI":"10.1007\/11847250_22"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00207-1"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.016"},{"key":"ref17","unstructured":"A. Dawar and S. Kreutzer, Domination problems in nowhere-dense classes, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15\u201317, 2009, IIT Kanpur, India, LIPIcs. Leibniz Int. Proc. Inform. 4, R. Kannan and K. N. Kumar, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2009, pp. 157\u2013168, https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2009.2315."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.02.001"},{"key":"ref23","first-page":"141","volume":"3","author":"Fellows M. R.","year":"1991","journal-title":"Australas. J. Combin."},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Bidimensionality and kernels, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, TX, USA, January 17\u201319, 2010, M. Charikar, ed. SIAM, Philadelphia, 2010, pp. 503\u2013510, https:\/\/doi.org\/10.1137\/1.9781611973075.43.","DOI":"10.1137\/1.9781611973075.43"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/3155298"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419649"},{"key":"ref27","unstructured":"J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein, Finding cliques in social networks: A new distribution-free model, in 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic, LIPIcs. Leibniz Int. Proc. Inform. 107, I. Chatzigiannakis, C. C. Kaklamanis, D. Marx, and D. Sannella, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2018, 55, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.55."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210459"},{"key":"ref29","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.017"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"P. A. Golovach and Y. Villanger, Parameterized complexity for domination problems on degenerate graphs, in Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008, Revised Papers, Lecture Notes in Comput. Sci. 5344, H. Broersma, T. Erlebach, T. Friedetzky, and D. Paulusma, eds. Springer, Berlin, 2008, pp. 195\u2013205, https:\/\/doi.org\/10.1007\/978-3-540-92248-3_18.","DOI":"10.1007\/978-3-540-92248-3_18"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"Q. Gu and N. Imani, Connectivity is not a limit for kernelization: Planar connected dominating set, in LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19\u201323, 2010. Proceedings, Lecture Notes in Comput. Sci. 6034, A. L\u00f3pez-Ortiz, ed. Springer, Berlin, 2010, pp. 26\u201337, https:\/\/doi.org\/10.1007\/978-3-642-12200-2_4.","DOI":"10.1007\/978-3-642-12200-2_4"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"J. Guo and R. Niedermeier, Linear problem kernels for NP-hard problems on planar graphs, in Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9\u201313, 2007, Proceedings, Lecture Notes in Comput. Sci. 4596, L. Arge, C. Cachin, T Jurdzinski, and A. Tarlecki, eds. Springer, Berlin, 2007, pp. 375\u2013386, https:\/\/doi.org\/10.1007\/978-3-540-73420-8_34.","DOI":"10.1007\/978-3-540-73420-8_34"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1309-3"},{"key":"ref35","unstructured":"E. Husic and T. Roughgarden, FPT Algorithms for Finding Fense Subgraphs in c-Closed Graphs, preprint, arXiv:2007.09768 [math.CO], 2020."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830917500306"},{"key":"ref37","unstructured":"L. Kanesh, J. Madathil, S. Roy, A. Sahu, and S. Saurabh, Further exploiting c-closure for FPT algorithms and kernels for domination problems, in 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15\u201318, 2022, Marseille, France (Virtual Conference), LIPIcs. Leibniz Int. Proc. Inform. 219, P. Berenbrink and B. Monmege, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2022, 39, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.39."},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"I. A. Kanj and L. Perkovic, Improved parameterized algorithms for planar dominating set, in Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26\u201330, 2002, Proceedings, Lecture Notes in Comput. Sci. 2420, K. Diks and W. Rytter, eds. Springer, Berlin, 2002, pp. 399\u2013410, https:\/\/doi.org\/10.1007\/3-540-45687-2_33.","DOI":"10.1007\/3-540-45687-2_33"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"J. Kneis, D. M\u00f6lle, S. Richter, and P. Rossmanith, Intuitive algorithms and t-vertex cover, in Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18\u201320, 2006, Proceedings, Lecture Notes in Comput. Sci. 4288, T. Asano, ed. Springer, Berlin, 2006, pp. 598\u2013607, https:\/\/doi.org\/10.1007\/11940128_60.","DOI":"10.1007\/11940128_60"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"J. Kneis, D. M\u00f6lle, and P. Rossmanith, Partial vs. complete domination: t-dominating set, in SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20\u201326, 2007, Proceedings, Lecture Notes in Comput. Sci. 4362, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, and F. Plasil eds. Springer, Berlin, 2007, pp. 367\u2013376, https:\/\/doi.org\/10.1007\/978-3-540-69507-3_31.","DOI":"10.1007\/978-3-540-69507-3_31"},{"key":"ref41","unstructured":"T. Koana, C. Komusiewicz, A. Nichterlein, and F. Sommer, Covering many (or few) edges with k vertices in sparse graphs, in 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15\u201318, 2022, Marseille, France (Virtual Conference), LIPIcs. Leibniz Int. Proc. Inform. 219, Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2022, 42, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.42."},{"key":"ref42","unstructured":"T. Koana, C. Komusiewicz, and F. Sommer, Computing dense and sparse subgraphs of weakly closed graphs, in 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14\u201318, 2020, Hong Kong, China (Virtual Conference), LIPIcs. Leibniz Int. Proc. Inform. 181, Y. Cao, S. Cheng, and M. Li, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2020, 20, https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.20."},{"key":"ref43","unstructured":"T. Koana, C. Komusiewicz, and F. Sommer, Exploiting c-closure in kernelization algorithms for graph problems, in 28th Annual European Symposium on Algorithms, ESA 2020, September 7\u20139, 2020, Pisa, Italy (Virtual Conference), LIPIcs. Leibniz Int. Proc. Inform. 173, F. Grandoni, G. Herman, and P. Sanders, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2020, 65, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.65."},{"key":"ref44","unstructured":"T. Koana, C. Komusiewicz, and F. Sommer, Essentially tight kernels for (weakly) closed graphs, in 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6\u20138, 2021, Fukuoka, Japan, LIPIcs. Leibniz Int. Proc. Inform. 212, Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2021, 35, https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.35."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/21M1449476"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.06.019"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, M. Mnich, and S. Saurabh, Linear kernel for planar connected dominating set, in Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18\u201322, 2009, Proceedings, Lecture Notes in Comput. Sci. 5532, J. Chen and S. B. Cooper, eds. Springer, Berlin, 2009, pp. 281\u2013290, https:\/\/doi.org\/10.1007\/978-3-642-02017-9_31.","DOI":"10.1007\/978-3-642-02017-9_31"},{"key":"ref48","unstructured":"D. Lokshtanov and V. Surianarayanan, Dominating set in weakly closed graphs is fixed parameter tractable, in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, December 15\u201317, 2021, Virtual Conference, LIPIcs. Leibniz Int. Proc. Inform. 213, M. Bojanczyk and C. Chekuri, eds. Leibniz-Zentrum f\u00fcr Informatik, Wadern, 2021, 29, https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2021.29."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00184-6"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9681-z"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9394-2"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9089-3"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390187"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9148-9"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1491721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:29:45Z","timestamp":1787318985000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1491721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,10]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/22M1491721"],"URL":"https:\/\/doi.org\/10.1137\/22m1491721","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,10]]}}}