In der klassischen Komplexitätstheorie unterscheiden wir zwischen der Klasse P von in Polynomialzeit lösbaren Problemen, und der Klasse NP-schwer von Problemen bei denen die allgemeine Annahme ist, dass diese nicht in Polynomialzeit lösbar sind. Allerdings sind viele Probleme, die wir lösen möchten, NP-schwer. Gleichzeitig besteht eine große Diskrepanz zwischen den empirisch beobachteten und den festgestellten worst-case Laufzeiten. Es ist bekannt, dass Vorverarbeitung oder Datenreduktion auf realen Instanzen zu Laufzeitverbesserungen führt. Hier stoßen wir an die Grenze der klassischen Komplexitätstheorie.
Der Fokus dieser Arbeit liegt auf Vorverarbeitungsalgorithmen für NP-schwere Probleme. Unser Ziel ist es, bestimmte Instanzen eines NP-schweren Problems vorverarbeiten zu können, indem wir die Struktur betrachten. Genauer gesagt, für eine gegebene Instanz und einen zusätzlichen Parameter l, möchten wir in Polynomialzeit eine äquivalente Instanz berechnen, deren Größe und Parameterwert nur durch eine Funktion im Parameterwert l beschränkt ist. In der parametrisierten Komplexitätstheorie heißen diese Algorithmen Kernelisierung.
Wir werden drei NP-schwere Graphenprobleme betrachten, nämlich Vertex Cover, Edge Dominating Set und Subset Feedback Vertex Set. Für Vertex Cover werden wir bekannte Ergebnisse für Kernelisierungen vereinheitlichen, wenn der Parameter die Größe einer Entfernungsmenge zu einer gegebenen Graphklasse ist. Anschließend untersuchen wir die Kernelisierbarkeit von Edge Dominating Set. Es stellt sich heraus, dass die Kernelisierbarkeit deutlich komplexer ist. Dennoch klassifizieren wir die Existenz einer polynomiellen Kernelisierung, wenn jeder Graph in der Graphklasse eine disjunkte Vereinigung von konstant großen Komponenten ist. Schließlich betrachten wir das Subset Feedback Vertex Set Problem und zeigen, dass es eine randomisierte polynomielle Kernelisierung hat, wenn der Parameter die Lösungsgröße ist. / In classical complexity theory, we distinguish between the class P, of polynomial-time solvable problems, and the class NP-hard, of problems where the widely-held belief is that we cannot solve these problems in polynomial time. Unfortunately, many of the problems we want to solve are NP-hard. At the same time, there is a large discrepancy between the empirically observed running times and the established worst-case bounds. Using preprocessing or data reductions on real-world instances is known to lead to huge improvements in the running time. Here we come to the limits of classical complexity theory.
In this thesis, we focus on preprocessing algorithms for NP-hard problems. Our goal is to find ways to preprocess certain instances of an NP-hard problem by considering the structure of the input instance. More precisely, given an instance and an additional parameter l, we want to compute in polynomial time an equivalent instance whose size and parameter value is bounded by a function in the parameter l only.
In the field of parameterized complexity, these algorithms are called kernelizations.
We will consider three NP-hard graph problems, namely Vertex Cover, Edge Dominating Set, and Subset Feedback Vertex Set. For Vertex Cover, we will unify known results for kernelizations when parameterized by the size of a deletion set to a specified graph class. Afterwards, we study the existence of polynomial kernelizations for Edge Dominating Set when parameterized by the size of a deletion set to a graph class. We point out that the existence of polynomial kernelizations is much more complicated than for Vertex Cover. Nevertheless, we fully classify the existence of polynomial kernelizations when every graph in the graph class is a disjoint union of constant size components. Finally, we consider graph cut problems, especially the Subset Feedback Vertex Set problem. We show that this problem has a randomized polynomial kernelization when the parameter is the solution size.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/22131 |
| Date | 22 May 2020 |
| Creators | Hols, Eva-Maria Christiana |
| Contributors | Kratsch, Stefan, Köbler, Johannes, Niedermeier, Rolf |
| Publisher | Humboldt-Universität zu Berlin |
| Source Sets | Humboldt University of Berlin |
| Language | English |
| Detected Language | German |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/pdf |
| Rights | (CC BY-NC-SA 4.0) Attribution-NonCommercial-ShareAlike 4.0 International, https://creativecommons.org/licenses/by-nc-sa/4.0/ |
Page generated in 0.0019 seconds