{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:41Z","timestamp":1771036361318,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/21"],"award-info":[{"award-number":["NI 369\/21"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KO 3669\/6"],"award-info":[{"award-number":["KO 3669\/6"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"abstract":"Abstract<\/jats:title>We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number\u00a0c<\/jats:italic> and weak closure number\u00a0$$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Fox et al. SIAM J Comput 49(2):448\u2013464, 2020) in addition to the standard parameter solution size\u00a0k<\/jats:italic>. The weak closure number\u00a0$$\\gamma $$<\/jats:tex-math>\n \u03b3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of a graph is upper-bounded by the minimum of its closure number\u00a0c<\/jats:italic> and its degeneracy\u00a0d<\/jats:italic>. For Capacitated Vertex Cover<\/jats:sc>, Connected Vertex Cover<\/jats:sc>, and Induced Matching<\/jats:sc> we obtain the first kernels of size\u00a0$$k^{\\mathcal {O}(\\gamma )}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$k^{\\mathcal {O}(\\gamma )}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and\u00a0$$(\\gamma k)^{\\mathcal {O}(\\gamma )}$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n \u03b3<\/mml:mi>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size $$k^{o(\\gamma )}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n \u03b3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1\u201343:22, 2017). For Capacitated Vertex Cover<\/jats:sc>, we show that even a kernel of size\u00a0$$k^{o(c)}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n c<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is unlikely. In contrast, for Connected Vertex Cover<\/jats:sc>, we obtain a kernel with\u00a0$$\\mathcal {O}(ck^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n c<\/mml:mi>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0vertices. Moreover, we prove that searching for an induced subgraph of order at least\u00a0k<\/jats:italic> belonging to a hereditary graph class\u00a0$$\\mathcal {G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> admits a kernel of size\u00a0$$k^{\\mathcal {O}(\\gamma )}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \u03b3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when\u00a0$$\\mathcal {G}$$<\/jats:tex-math>\n G<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set<\/jats:sc> on graphs with constant closure number\u00a0c<\/jats:italic> and kernels for Dominating Set<\/jats:sc> on weakly closed split graphs and weakly closed bipartite graphs.<\/jats:p>","DOI":"10.1007\/s00453-022-01088-7","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T11:03:39Z","timestamp":1673262219000},"page":"1706-1735","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Essentially Tight Kernels for (Weakly) Closed Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8684-0611","authenticated-orcid":false,"given":"Tomohiro","family":"Koana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-525X","authenticated-orcid":false,"given":"Frank","family":"Sommer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,9]]},"reference":[{"key":"1088_CR1","unstructured":"Behera, B., Husi\u0107, E., Jain, S., Roughgarden, T., Seshadhri, C.: FPT algorithms for finding near-cliques in $$c$$-closed graphs. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS\u00a022), volume 215 of LIPIcs, pp 17:1\u201317:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1088_CR2","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity (ECCC), 049 (2003)"},{"issue":"8","key":"1088_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"1088_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)"},{"issue":"3","key":"1088_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3108239","volume":"13","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Grandoni, F., Hermelin, D.: Tight Kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms 13(3), 1\u201322 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"15","key":"1088_CR6","doi-asserted-by":"publisher","first-page":"2131","DOI":"10.1016\/j.dam.2012.05.016","volume":"160","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in $$d$$-degenerate graphs. Discret. Appl. Math. 160(15), 2131\u20132141 (2012)","journal-title":"Discret. Appl. Math."},{"key":"1088_CR7","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201912), pp 68\u201381. SIAM (2012)","DOI":"10.1137\/1.9781611973099.6"},{"issue":"2","key":"1088_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization Lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 1\u201320 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"1088_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013)"},{"key":"1088_CR10","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics 18 (2013)","DOI":"10.1145\/2543629"},{"issue":"1","key":"1088_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"1","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Rado, R.: Intersection theorems for systems of sets. J. Lond. Math. Soc. 1(1), 85\u201390 (1960)","journal-title":"J. Lond. Math. Soc."},{"issue":"1\u20132","key":"1088_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","volume":"25","author":"P Erd\u00f6s","year":"1989","unstructured":"Erd\u00f6s, P., Hajnal, A.: Ramsey-type theorems. Discret. Appl. Math. 25(1\u20132), 37\u201352 (1989)","journal-title":"Discret. Appl. Math."},{"issue":"18","key":"1088_CR13","doi-asserted-by":"publisher","first-page":"1994","DOI":"10.1016\/j.dam.2010.08.026","volume":"158","author":"R Erman","year":"2010","unstructured":"Erman, R., Kowalik, \u0141, Krnc, M., Wale\u0144, T.: Improved induced matchings in sparse graphs. Discret. Appl. Math. 158(18), 1994\u20132003 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"7","key":"1088_CR14","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/j.dam.2010.04.015","volume":"159","author":"EM Eschen","year":"2011","unstructured":"Eschen, E.M., Ho\u00e0ng, C.T., Spinrad, J.P., Sritharan, R.: On graphs without a $$C_4$$ or a diamond. Discret. Appl. Math. 159(7), 581\u2013587 (2011)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1088_CR15","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/18M1210459","volume":"49","author":"J Fox","year":"2020","unstructured":"Fox, J., Tim Roughgarden, C., Seshadhri, F.W., Wein, N.: Finding cliques in social networks: a new distribution-free model. SIAM J. Comput. 49(2), 448\u2013464 (2020)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1088_CR16","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P Frankl","year":"1981","unstructured":"Frankl, P., Wilson, R.M.: Intersection theorems with geometric consequences. Combinatorica 1(4), 357\u2013368 (1981)","journal-title":"Combinatorica"},{"key":"1088_CR17","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201912), pp 104\u2013113. SIAM (2012)","DOI":"10.1137\/1.9781611973099.9"},{"issue":"6","key":"1088_CR18","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1016\/j.jcss.2010.09.001","volume":"77","author":"IA Kanj","year":"2011","unstructured":"Kanj, I.A., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. J. Comput. Syst. Sci. 77(6), 1058\u20131070 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1088_CR19","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theoret. Comput. Sci. 289(2), 997\u20131008 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"1088_CR20","unstructured":"Koana, T., Komusiewicz, C., Sommer, F.: Computing dense and sparse subgraphs of weakly closed graphs. In: Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC\u00a0\u201920), volume 181 of LIPIcs, pp 20:1\u201320:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"4","key":"1088_CR21","doi-asserted-by":"publisher","first-page":"2798","DOI":"10.1137\/21M1449476","volume":"36","author":"T Koana","year":"2022","unstructured":"Koana, T., Komusiewicz, C., Sommer, F.: Exploiting $$c$$-closure in kernelization algorithms for graph problems. SIAM J. Discret. Math. 36(4), 2798\u20132821 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"1088_CR22","first-page":"1","volume":"10","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S.: Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. ACM Trans. Algorithms 10(4), 1\u201316 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"1088_CR23","unstructured":"Kratsch, S.: Recent developments in kernelization: a survey. Bull. EATCS, 113 (2014)"},{"issue":"1","key":"1088_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2691321","volume":"7","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S., Pilipczuk, M., Rai, A., Raman, V.: Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. ACM Trans. Comput. Theory 7(1), 1\u201318 (2014)","journal-title":"ACM Trans. Comput. Theory"},{"key":"1088_CR25","unstructured":"Lokshtanov, D., Surianarayanan, V.: Dominating set in weakly closed graphs is fixed parameter tractable. In: Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u00a0\u201921), volume 213 of LIPIcs, pp 29:1\u201329:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"1","key":"1088_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2390176.2390187","volume":"9","author":"G Philip","year":"2012","unstructured":"Philip, G., Raman, V., Sikdar, S.: Polynomial Kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms 9(1), 1\u201323 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1088_CR27","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01088-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01088-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01088-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:35:10Z","timestamp":1685158510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01088-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1088"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01088-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"20 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}