Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
| dc.contributor.advisor | Niedermeier, Rolf | |
| dc.contributor.author | Fluschnik, Till | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Niedermeier, Rolf | |
| dc.contributor.referee | Jansen, Bart M. P. | |
| dc.contributor.referee | Szeider, Stefan | |
| dc.date.accepted | 2019-11-29 | |
| dc.date.accessioned | 2020-06-23T13:44:26Z | |
| dc.date.available | 2020-06-23T13:44:26Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | Preprocessing and data reduction are basic algorithmic tools. In parameterized algorithmics, such preprocessing is defined by (problem) kernelization, where an equivalent instance (the kernel) is computed in polynomial time and its size can be upper-bounded only in a function of the parameter value of the input instance. In this thesis, we study lower and upper bounds on kernelization regarding polynomial-sized kernels as well as variants of kernelization like kernelization for polynomial-time solvable problems. We introduce a new family of fractal-like graphs that we call T-fractals. Using these T-fractals in a common machinery for proving kernelization lower bounds, we refute (under some complexity-theoretic assumptions) the existence of polynomial kernels for some distance-related cut problems. One of these problems is the Length-Bounded Edge-Cut problem, for which the status of polynomial kernelization remained unknown for some time. We underline and extend the usage of the so-called diminisher framework for excluding restrictive kernels of polynomial size under the assumption of P being different to NP. We prove that the original framework applies to more parameterized problems than previously known. In order to exclude less restrictive kernels of polynomial size, we extend the framework. We prove, however, that this extended framework does not apply to several parameterized problems. Yet, we prove that the framework applies to polynomial-time solvable problems, yielding first direct kernelization lower bounds in this class of problems. In addition, we prove a kernelization dichotomy regarding the running time and the size of the kernel for the polynomial-time solvable problem of computing the hyperbolicity of a graph. Finally, we study classic graph problems under the so-called secluded concept, where constraints on the neighborhood of the subgraph in question are present. One of our problems is a secluded variant of the classic problem of finding a short path connecting two terminal vertices. For this problem, we prove a hierarchy of polynomial kernelizations regarding several structural graph parameters. Herein, we obtain polynomial kernels via the so-called “losing weight” technique. We outline this technique and prove that it applies to more problems than previously known. Eventually, we study two more problems in the secluded setup and prove how different constraints on the neighborhood lead to different complexity-theoretic classifications not only regarding polynomial kernelizability. | en |
| dc.description.abstract | Algorithmische Lösungsverfahren für Entscheidungs- oder Optimierungsprobleme nutzen oft eine Datenvorverarbeitung um eine Eingabeinstanz auf ihren wesentlichen Kern zu bringen. In der parametrisierten Komplexität ist diese Vorverarbeitung definiert als (Problem-) Kernelisierung. Sie gehört zu den meistgenutzten algorithmischen Werkzeugen. Die vorliegenen Dissertation befasst sich mit oberen und unteren Schranken für polynomielle Kernelisierung (d.h. für Kernelisierung die eine äquivalente Instanz liefert deren Größe polynomiell im Parameter beschränkt ist) sowie mit Varianten von Kernelisierung, z.B. für polynomzeitlösbare Probleme. Wir entwickeln eine Familie von Graphen, die sogenannten „T-fractals“, die wie Fraktale eine selbstähnliche Struktur haben. Mittels dieser T-fractals beweisen wir untere Schranken für polynomielle Kernelisierung für einige Probleme bei denen es das Ziel ist, durch eine kleine Anzahl von Kantenlöschungen gewisse Knotendistanzen zu maximieren. Eines dieser Probleme ist das Length-Bounded Edge-Cut, dessen polynomielle Kernelisierbarkeit länger offen war. Zusätzlich erweitern wir das sogenannte „Diminisher“-Konzept zum Ausschließen polynomieller Kernelisierungsvarianten unter der Annahme dass P nicht gleich NP ist. Bei den Varianten handelt es sich um Kernelisierungen, bei denen der Parameter in der resultierenden Instanz nicht vergrößert werden darf, sprich restriktive Kernelisierungen. Zunächst zeigen wir, dass das Diminisher-Konzept auf mehr als die zuvor bekannten Probleme anwendbar ist. Darüber hinaus erweitern wir das Konzept zur Anwendung auf weniger restriktive Kernelisierungen. Wir stellen dabei fest, dass das erweiterte Konzept zwar oft unter gewissen Annahmen nicht anwendbar ist, sich jedoch für den Bereich der polynomzeitlösbaren Probleme als nutzbar erweist. In diesem Bereich zeigen wir für ein Problem eine Kernelisierungsdichotomie bezüglich Laufzeit und Größe der Kernelisierung. Zuletzt studieren wir klassische Graphprobleme unter Einschränkungen auf die Nachbarschaft des gesuchten Teilgraphen. Eines unserer Probleme ist das klassische Problem des Findens eines kürzesten Weges, der zwei ausgewählte Knoten verbindet. Für dieses Problem beweisen wir eine Hierarchie von strukturellen Graphparametern bezüglich polynomieller Kernelisierung. Einige der dabei erzielten polynomiellen Kernelisierungen nutzen eine Technik zur Reduzierung von Gewichten in Graphen. Wir präsentieren diese Technik und zeigen neue Berechnungsprobleme auf, für die die Technik anwendbar ist. Zuletzt zeigen wir noch für zwei weitere klasssiche Graphprobleme auf, wie Einschränkungenauf die Nachbarschaft der Lösungsstruktur sich unter anderem auf polynomielle Kernelisierung auswirken können. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/11246 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-10134 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | computationally hard problems | en |
| dc.subject.other | parameterized algorithmics | en |
| dc.subject.other | problem kernelization | en |
| dc.subject.other | berechnungsschwere Probleme | de |
| dc.subject.other | parametrisierte Algorithmik | de |
| dc.subject.other | Problemkernelisierung | de |
| dc.title | Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods | en |
| dc.title.translated | Elemente der effizienten Datenreduktion: Fraktale, Verminderer, Gewichte und Nachbarschaften | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Algorithmik und Komplexitätstheorie | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.group | FG Algorithmik und Komplexitätstheorie | de |
| tub.affiliation.institute | Inst. Softwaretechnik und Theoretische Informatik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |