2026-07-23T12:40:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12931 2024-03-06T10:51:07Z ddc:004 open_access

Exploiting c-Closure in Kernelization Algorithms for Graph Problems Koana, Tomohiro Komusiewicz, Christian Sommer, Frank Fixed-parameter tractability kernelization c-closure Dominating Set Induced Matching Irredundant Set Ramsey numbers A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput. '20] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^𝒪(c), that Induced Matching admits a kernel with 𝒪(c⁷ k⁸) vertices, and that Irredundant Set admits a kernel with 𝒪(c^{5/2} k³) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomohiro Koana and Christian Komusiewicz and Frank Sommer 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.65 urn:nbn:de:0030-drops-129316 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.65 eng https://creativecommons.org/licenses/by/3.0/legalcode