2026-07-25T09:17:54Z https://drops.dagstuhl.de/oai

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

A General Kernelization Technique for Domination and Independence Problems in Sparse Classes Einarson, Carl Reidl, Felix Dominating Set Independence Kernelization Bounded Expansion We unify and extend previous kernelization techniques in sparse classes [Jochen Alber et al., 2004; Pilipczuk and Siebertz, 2018] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r,c)-Dominating Set, (r,c)-Scattered Set, Total r-Domination, r-Roman Domination, and a problem we call (r,[λ,μ])-Domination (implying a bikernel for r-Perfect Code). At the cost of slightly changing the output graph class our bikernels can be turned into kernels. We also demonstrate how these constructions can be combined to create "multikernels", meaning graphs that represent kernels for multiple problems at once. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carl Einarson and Felix Reidl 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.11 urn:nbn:de:0030-drops-133142 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode