Kernelization of generic problems [Elektronische Ressource] : upper and lower bounds / vorgelegt von Stefan Kratsch

Stefan Kratsch

Sujets

• Informatik

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2010
• Nombre de lectures: 15
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Kernelization of Generic
Problems
Upper and Lower Bounds
Dissertation
zur Erlangung des Grades des
Doktors der Naturwissenschaften (Dr. rer. nat.)
der Naturwissenschaftlich-Technischen Fakult aten
der Universit at des Saarlandes
vorgelegt von
Stefan Kratsch
Saarbruc ken
2010Tag des Kolloquiums: 30. August 2010
Dekan:
Professor Dr. Holger Hermanns
Berichterstatter:
Professor Dr. Kurt Mehlhorn, Max-Planck-Institut fur Informatik, Saarbruc ken Dr. Hans L. Bodlaender, Utrecht University, Utrecht, the Netherlands
Dr. Jiong Guo, Cluster of Excellence (MMCI), Saarbruc ken
Vorsitz:
Professor Dr. Raimund Seidel, Saarland University, Saarbruc ken
Akad. Mitarbeiter:
Ben Galehouse Ph.D., Max-Planck-Institut fur Informatik, Saarbruc kenTo my parentsZusammenfassung
Diese Dissertation besch aftigt sich mit der Kernelisierbarkeit von generischen Problemen,
de niert durch syntaktische Beschr ankungen oder als Problemsystem. Polynomielle Ker-
nelisierung ist eine Formalisierung des Konzepts der Datenreduktion fur kombinatorisch
schwierige Probleme. Sie erlaubt eine grundlic he Untersuchung dieses wichtigen und
fundamentalen Begri s. Die Dissertation gliedert sich in zwei Hauptteile.
Im ersten Teil beweisen wir, dass alle Probleme aus zwei syntaktischen Teilklassen der
Menge aller konstantfaktor-approximierbaren Probleme polynomielle Kernelisierungen
haben. Die Probleme mussen durch Optimierung ub er Formeln in Pr adikatenlogik ers-
ter Stufe mit beschr ankter Quanti zierung beschreibbar sein. Eine Relaxierung dieser
Beschr ankungen gestattet bereits Probleme, die keine polynomielle Kernelisierung er-
lauben. Im Anschluss betrachten wir Kantenmodi zierungsprobleme und zeigen, dass
diese im Allgemeinen keine polynomielle Kernelisierung haben.
Im zweiten Teil betrachten wir drei Arten von booleschen Constraint-Satisfaction-
Problemen. Wir charakterisieren vollst andig welche dieser Probleme polynomielle Ker-
nelisierungen erlauben. Fur jedes gegebene Problem zeigen unsere Resultate entweder
eine polynomielle Kernelisierung oder sie zeigen, dass das Problem keine polynomielle
Kernelisierung hat. Die Dichotomien sind durch Eigenschaften der erlaubten Constraints
charakterisiert.
Die Arbeit ist in englischer Sprache verfasst.
ivAbstract
This thesis addresses the kernelization properties of generic problems, de ned via syntac-
tical 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 rst part we prove that all problems from two syntactically de ned classes of
constant-factor approximable problems admit polynomial kernelizations. The problems
must be expressible via optimization over rst-order formulas with restricted quanti -
cation; when relaxing these restrictions we nd problems that do not admit polynomial
kernelizations. Next, we consider edge modi cation 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.
The thesis is written in English.
vAcknowledgments
First of all I wish to thank Kurt Mehlhorn for giving me both motivating supervision and
helpful advice as well as the freedom and con dence that made this thesis possible. I am
grateful to Magnus Wahlstr om for introducing me to constraint satisfaction problems and
for the patience this required. Similarly, I have to thank Pascal Schweitzer for sharing
his insight into graph isomorphism and related problems of unknown complexity. I found
it a pleasure to be a part of the algorithms and complexity group at MPI, in research
as well as in social activities. I am greatly indebted to my parents for their ongoing
support, encouragement, and advice; not least for reminding me to take the occasional
vacation.
Finally, I want to thank the usual suspects for our long evenings of applied game
theory; with a special thanks to the monster for not eating all the meeples.
viContents
I. Introduction 1
II. Upper and lower bounds for kernelization 11
1. Parameterized complexity and kernelization 13
1.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2. Parameterized complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3. Kernelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4. Polynomial lower bounds for kernelization . . . . . . . . . . . . . . . . . . 21
2. Sun owers 27
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2. Application in kernelization . . . . . . . . . . . . . . . . . . . . . . . . . . 31
+3. Polynomial kernelizations for MIN F and MAX NP 331
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2. Syntactical problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
+
3.3. Polynomial kernelization for MIN F . . . . . . . . . . . . . . . . . . . 371
3.4. P k for MAX NP . . . . . . . . . . . . . . . . . . . . 42
3.5. Linear kernelization for MAX SNP . . . . . . . . . . . . . . . . . . . . . . 48
3.6. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4. Lower bounds for edge modi cation problems 51
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2. Hardness of Not-1-In-3 SAT . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3. Lower bounds for two H-free modi cation problems . . . . . . . . . . . . . 57
4.4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
III. Kernelizability of Boolean constraint satisfaction problems 63
5. Boolean constraint satisfaction problems 65
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2. De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
viiContents
6. Min ones constraint satisfaction problems 75
6.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2. Mergeability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.3. Characterization I: Polynomial kernelization . . . . . . . . . . . . . . . . . 78
6.4. II: Lower bound . . . . . . . . . . . . . . . . . . . . . . . 85
6.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7. Max ones constraint satisfaction problems 97
7.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.2. Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.3. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8. Exact ones constraint satisfaction problems 107
8.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.2. De nitions and related results . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.3. Characterization I: Zero-valid, Horn, and width-2 a ne . . . . . . . . . . 110
8.4. II: Remaining cases . . . . . . . . . . . . . . . . . . . . . 114
8.5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
IV. Conclusion and open problems 121
9. Conclusion 123
+9.1. Beyond MIN F and MAX NP . . . . . . . . . . . . . . . . . . . . . . 1241
9.2. Kernelization and approximation revisited . . . . . . . . . . . . . . . . . . 127
10.Open problems and further research 129
Bibliography 135
viiiPart I.
Introduction
1