TY  - THES
T1  - Kernelization of generic problems : upper and lower bounds
A1  - Kratsch,Stefan
Y1  - 2011/01/21
N2  - This thesis addresses the kernelization properties of generic problems, defined via syntactical restrictions or by a problem framework. Polynomial kernelization is a formalization of data reduction, aimed at combinatorially hard problems, which allows a rigorous study of this important and fundamental concept. The thesis is organized into two main parts. In the first part we prove that all problems from two syntactically defined classes of constant-factor approximable problems admit polynomial kernelizations. The problems must be expressible via optimization over first-order formulas with restricted quantification; when relaxing these restrictions we find problems that do not admit polynomial kernelizations. Next, we consider edge modification problems, and we show that they do not generally admit polynomial kernelizations. In the second part we consider three types of Boolean constraint satisfaction problems.We completely characterize whether these problems admit polynomial kernelizations, i.e.,given such a problem our results either provide a polynomial kernelization, or they show that the problem does not admit a polynomial kernelization. These dichotomies are characterized by properties of the permitted constraints.
KW  -  Kernel <Informatik>
KW  - Datenkompression
KW  - Prädikatenlogik
KW  - Constraint-Erfüllung
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/3530
ER  -