Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
R. Ganian, F. Slivovsky, St. Szeider:
"Meta-kernelization with Structural Parameters";
Vortrag: International Symposium on Mathematical Foundations of Computer Science (MFCS),
Klosterneuburg, Austria;
26.08.2013
- 30.08.2013; in: "The 38th International Symposium on Mathematical Foundations of Computer Science, Proceedings",
K. Chatterjee, J. Sgall (Hrg.);
Springer / LNCS,
8087
(2013),
ISBN: 978-3-642-40312-5;
S. 457
- 468.
Kurzfassung englisch:
Meta-kernelization theorems are general results that provide polynomial kernels for large classes of parameterized problems. The known meta-kernelization theorems, in particular the results of Bodlaender et al. (FOCS'09) and of Fomin et al. (FOCS'10), apply to optimization problems parameterized by solution size. We present the first meta-kernelization theorems that use a structural parameters of the input and not the solution size.
Let C be a graph class. We define the C-cover number of a graph to be a the smallest number of modules the vertex set can be partitioned into, such that each module induces a subgraph that belongs to the class C.
We show that each graph problem that can be expressed in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the C-cover number for any fixed class C of bounded rank-width (or equivalently, of bounded clique-width, or bounded Boolean width). Many graph problems such as Independent Dominating Set, c-Coloring, and c-Domatic Number are covered by this meta-kernelization result.
Our second result applies to MSO expressible optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We show that these problems admit a polynomial annotated kernel with a linear number of vertices.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-40313-2_41
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.