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.STACS.2014.312
URN: urn:nbn:de:0030-drops-44675
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4467/
Go to the corresponding LIPIcs Volume Portal

Garnero, Valentin ; Paul, Christophe ; Sau, Ignasi ; Thilikos, Dimitrios M.

Explicit Linear Kernels via Dynamic Programming

pdf-format:
25.pdf (0.7 MB)

Abstract

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result [Bodlaender et al., FOCS 2009] on graphs of bounded genus, then generalized by [Fomin et al., SODA 2010] to graphs excluding a fixed minor, and by [Kim et al., ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants.

In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for Planar-F-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

BibTeX - Entry

@InProceedings{garnero_et_al:LIPIcs:2014:4467,
  author =	{Valentin Garnero and Christophe Paul and Ignasi Sau and Dimitrios M. Thilikos},
  title =	{{Explicit Linear Kernels via Dynamic Programming}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{312--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4467},
  URN =		{urn:nbn:de:0030-drops-44675},
  doi =		{10.4230/LIPIcs.STACS.2014.312},
  annote =	{Keywords: parameterized complexity, linear kernels, dynamic programming, protrusion replacement, graph minors}
}

Keywords: parameterized complexity, linear kernels, dynamic programming, protrusion replacement, graph minors
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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