DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2020.11

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

Authors: Carl Einarson and Felix Reidl

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

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.

Cite as

Carl Einarson and Felix Reidl. A General Kernelization Technique for Domination and Independence Problems in Sparse Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{einarson_et_al:LIPIcs.IPEC.2020.11,
  author =	{Einarson, Carl and Reidl, Felix},
  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 =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.11},
  URN =		{urn:nbn:de:0030-drops-133142},
  doi =		{10.4230/LIPIcs.IPEC.2020.11},
  annote =	{Keywords: Dominating Set, Independence, Kernelization, Bounded Expansion}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2019.40

Domination Above r-Independence: Does Sparseness Help?

Authors: Carl Einarson and Felix Reidl

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract

Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maximal r-independent set X (a set in which all vertices have pairwise distance at least r+1) along the input graph G which, for r >= 2, lower-bounds the minimum size of any dominating set of G. In the spirit of gap-parameters, we consider a parametrisation by the size of the "residual" set R := V(G) \ N[X]. Our work aims to answer two questions: How does the constant r affect the tractability of the problem and does the restriction to sparse graph classes help here? For the base case r = 2, we find that the problem is paraNP-complete even in apex- and bounded-degree graphs. For r = 3, the problem is W[2]-hard for general graphs but in FPT for nowhere dense classes and it admits a linear kernel for bounded expansion classes. For r >= 4, the parametrisation becomes essentially equivalent to the natural parameter, the size of the dominating set.

Cite as

Carl Einarson and Felix Reidl. Domination Above r-Independence: Does Sparseness Help?. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{einarson_et_al:LIPIcs.MFCS.2019.40,
  author =	{Einarson, Carl and Reidl, Felix},
  title =	{{Domination Above r-Independence: Does Sparseness Help?}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.40},
  URN =		{urn:nbn:de:0030-drops-109840},
  doi =		{10.4230/LIPIcs.MFCS.2019.40},
  annote =	{Keywords: Dominating Set, Above Guarantee, Kernel, Bounded Expansion, Nowhere Dense}
}

Search Results

Documents authored by Einarson, Carl

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

Abstract

Cite as

Domination Above r-Independence: Does Sparseness Help?

Abstract

Cite as

Thanks for your feedback!

Could not send message