License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.11
URN: urn:nbn:de:0030-drops-133142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13314/
Go to the corresponding LIPIcs Volume Portal

Einarson, Carl ; Reidl, Felix

A General Kernelization Technique for Domination and Independence Problems in Sparse Classes

pdf-format:
LIPIcs-IPEC-2020-11.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{einarson_et_al:LIPIcs:2020:13314,
  author =	{Carl Einarson and Felix Reidl},
  title =	{{A General Kernelization Technique for Domination and Independence Problems in Sparse Classes}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13314},
  URN =		{urn:nbn:de:0030-drops-133142},
  doi =		{10.4230/LIPIcs.IPEC.2020.11},
  annote =	{Keywords: Dominating Set, Independence, Kernelization, Bounded Expansion}
}

Keywords: Dominating Set, Independence, Kernelization, Bounded Expansion
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI