direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Explicit Linear Kernel via Dynamic Programming

Valentin Garnero (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM))

In the last years several meta-results appeared on kernelization. These theorems guarantee the existence of a kernel for many problems on sparse graphs satisfying some general conditions. But as a price of generality, the algorithms are not explicit. In our results we propose a first step for explicitness using Dynamic Programming instead of Monadic Second Order Logic machinery.

After a short reminder on kernelization, I will present the schema of the previous existential theorem: "Meta-Kernelization", I will try to emphasize the points where non-explicitness occur and provide the idea to patch it, then I will start the formalization of our result, using Dominating Set as a running example.

Abstract of the corresponding article
Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of 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, manly due to their generality, it is not known 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 and Planar-F-Packing on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

25.09.2013 14:15
Valentin Garnero
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras