Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3922
Main Title: Exploring parameter spaces in coping with computational intractability
Translated Title: Exploration von Parameterräumen zur Handhabung von Berechnungsschweren Problemen
Author(s): Hartung, Sepp
Advisor(s): Niedermeier, Rolf
Referee(s): Niedermeier, Rolf
Heggernes, Pinar
Kratsch, Dieter
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In dieser Arbeit werden verschiedene Ansätze zur Identifikation von effizient lösbaren Spezialfällen für schwere Berechnungsprobleme untersucht. Dabei liegt der Schwerpunkt der Betrachtungen auf der Ermittlung des Einflusses sogenannter Problemparameter auf die Berechnungsschwere. Für Betrachtungen dieser Art bietet die parametrisierte Komplexitätstheorie unsere theoretische Basis. In der parametrisierten Komplexitätstheorie wird versucht sogenannte Problemparameter in schweren Berechnungsproblemen (meistens, NP-schwer) zu identifizieren und diese zur Entwicklung von parametrisierten Algorithmen zu nutzen. Parametrisierte Algorithmen sind dadurch gekennzeichnet, dass der exponentielle Laufzeitanteil durch eine Funktion abhängig allein vom Problemparameter beschränkt werden kann. Die Entwicklung von parametrisierten Algorithmen ist stark motiviert durch sogenannte heuristische Algorithmen. Heuristische Algorithmen weisen auf praktisch relevanten Probleminstanzen ein oft effizientes Laufzeitverhalten mit einer akzeptablen Lösungsqualität auf. Die dafür plausibelste Erklärung ist, dass praktische Instanzen nur selten den jeweils "ungünstigsten" Instanzen entsprechen, sondern oft gewisse anwendungsspezifische Strukturen aufweisen. Die Identifikation solcher Problemparameter und das Ausnutzen dieser Strukturen, welche durch kleine Parameterwerte impliziert werden, ist das Hauptanliegen der parametrisierten Algorithmik. In dieser Arbeit werden drei Ansätze zur Identifikation dieser Problemparameter vorgestellt und sie werden exemplarisch auf vier NP-schwere Probleme angewendet. Jeder dieser vier Ansätze führt zu einem sogenannten "Parameterraum". Dieser bezeichnet eine Menge von Problemparametern, welche untereinander in Beziehung stehen in einer Art und Weise, welche das automatische Übertragen von Härteergebnissen aber auch von Machbarkeitsergebnissen erlaubt. Damit ermöglicht der Begriff des Parameterraumes eine systematische und strukturierte Darstellung der parametrisierten Komplexität eines Problems. Nachfolgend werden die behandelten Probleme und die dazugehörigen Ergebnisse beschrieben. Der erste Ansatz zur Identifikation von Problemparametern studiert Graphprobleme in ihren Einschränkungen auf spezielle Graphklassen. Dieser Ansatz wird durch die Anwendung auf das Metric Dimension-Problem vorgeführt. Wir beweisen, dass Metric Dimension, selbst auf bipartiten Graphen mit Maximalknotengrad drei, keinen parametrisierten Algorithmus für den Parameter Lösungsgröße besitzen kann (unter der Annahme dass W[2] ungleich FPT). Durch die erwähnte Reduktion wird zusätzlich ein Inapproximationsergebnis impliziert. Der zweite Ansatz zur Identifikation von Problemparametern untersucht den Einfluss sogenannter struktureller Parameter auf die Berechnungsschwere eines Problems. Die Idee hier ist, die Häufigkeit des Auftretens gewisser Strukturen als Parameter zu verwenden. Der Ansatz der strukturellen Parametrisierung wird anhand zweier Probleme diskutiert. Im Detail werden ein Graphproblem namens 2-Club und das Zahlenproblem Vector (Positive) Explanation betrachtet. Bei 2-Club sucht man in einem gegebenen Graphen einen großen Teilgraphen mit Durchmesser höchstens zwei. 2-Club besitzt Anwendungen in der Analyse von sozialen und biologischen Netzwerken. Der untersuchte Raum der strukturellen Parameter für 2-Club ist sehr umfangreich und beinhaltet neben Graphparametern wie Baumweite und degeneracy auch Parameter welche sich aus dem Paradigma der "Distanz zu einfachen Instanzen" - Parametrisierung ableiten. Neben Härteergebnissen präsentieren wir auch mehrere parametrisierte Lösungsalgorithmen für 2-Club. Weiterhin wird eine effiziente Implementierung von parametrisierten Algorithmen für 2-Club vorgestellt. Als zweites wird eine Anwendung des strukturellen Parametrisierungsansatzes auf das Vector (Positive) Explanation Problem diskutiert. Wir geben einen parametrisierten Algorithmus für den Parameter "größter Abstand zwischen zwei aufeinanderfolgenden Zahlen im Eingabevektor" an und verbessern damit einen bereits bekannten Algorithmus. Wir betrachten zusätzlich Parametrisierungen, welche dem Paradigma der "Distanz zu einfachen Instanzen" folgen. Hierfür zeigen wir Härteergebnisse und weisen nach, dass sich zwei bekannte Problemvarianten in ihrer parametrisierten Komplexität unterscheiden. Der dritte Ansatz betrachtet den Einfluss verschiedener Nachbarschaftsstrukturen auf die parametrisierte Komplexität von Algorithmen, welche auf dem Prinzip der lokalen Suche basieren. Wir untersuchen den Einfluss verschiedener Nachbarschaftsstrukturen auf eine lokale Suchvariante des bekannten Traveling Salesman-Problems, LocalTSP genannt. Wir beschreiben einen Parameterraum und weisen nach, dass es für die meisten der darin enthaltenen Nachbarschaftsstrukturen (vermutlich) keinen parameterisierten Algorithmus gibt. Weiterhin untersuchen wir die Berechnungsschwere von LocalTSP auf planaren Graphen.
This thesis is about systematic approaches to identify tractable cases of computationally hard problems. It studies the influence of specific parameters on the computational complexity of the problems. Hence, parameterized complexity provides a natural and fruitful framework which forms the theoretical basis of our investigations. In a nutshell, parameterized algorithmics deals with identifying parameters in computationally hard problems (mostly, so-called NP-hard problems) and exploits them in order to design parameterized algorithms whose (presumably) unavoidable exponential running time part solely depends on a parameter value. This approach is strongly motivated by the often observed phenomenon that, when dealing with NP-hard problems in practical applications, so-called heuristic algorithms which are tuned to characteristics of the input data are well-performing, both in terms of running time as well as solution quality. The most plausible explanation for this behavior is that problem instances emerging from practical applications are not worst-case instances but rather admit certain, possibly application-specific, structures. Exploiting small parameter values that are implied by these structures for the development of exact and "efficient" solving algorithms is the central concern of parameterized algorithmics. In this thesis we describe three approaches to identify structures which determine the computational complexity of a problem. These three approaches naturally lead to so-called parameter spaces, that is, several parameters that are related to each other in some way which may allow to transfer tractability and intractability results between them. Hence they pave the way for a systematic and clear analysis of computational complexity and they help to chart the "border of intractability". We next describe our three approaches to identify tractable cases of NP-hard problems and outline our corresponding case studies. The first approach is tuned for graph problems and suggests to consider the computational complexity of an NP-hard graph problem, when restricted to a special graph class. In our first case study we prove that the Metric Dimension problem is (presumably) parameterized intractable with respect to the solution size parameter even on the special graph class of bipartite graphs with maximum degree three. In addition to this parameterized intractability result, from the same hardness reduction we obtain an (asymptotically) tight approximation lower bound. The second approach is denoted as structural parameterizations of the input. Structural parameterization deals with measuring the number of occurrences of a certain structure in the input. We perform the approach of structural parameterizations to two problems, a graph problem called 2-Club and a number problem called Vector (Positive) Explanation. 2-Club deals with finding large subgraphs of small diameter. One of the main applications of 2-Club is the analysis of social and biological networks. The corresponding structural parameter space consists of several well-known graph measurements such as treewidth (measuring how "tree-like" a graph is) and degeneracy (measuring the "sparsity" of a graph). In addition to these somehow classical graph parameters, in the spirit of the "distance from triviality" parameterization we consider parameters measuring the distance (number of vertex deletions) to special graph classes on which 2-Club is polynomial-time solvable. Besides computational intractability results, we provide a number of parameterized algorithms. We conclude with some positive empirical findings with an implementation of some 2-Club algorithms. We also apply the approach of structural parameterizations to a number problem called Vector (Positive) Explanation. This problem has applications in data warehousing and cancer radiation therapy. Extending previous work on the parameterized complexity of Vector (Positive) Explanation with respect to the maximum value parameter, we prove that Vector Explanation is fixed-parameter tractable by the stronger (smaller) parameter maximum difference between consecutive vector entries. We look at two "distance from triviality" parameters, obtaining NP-hardness results and revealing the fact that the complexity of two problem variants differ with respect to one of them. The third approach examines how the computational complexity of local search is influenced by different neighborhood structures. We conduct a systematic study of neighborhood structures of the local search variant of the famous Traveling Salesman problem, called LocalTSP. We describe well-known neighborhood structures and we arrange all of them into a parameter space. We then prove that LocalTSP is (presumably) parameterized intractable for most of these neighborhood structures. Furthermore, we examine the parameterized complexity of LocalTSP on planar graphs.
URI: urn:nbn:de:kobv:83-opus4-46440
http://depositonce.tu-berlin.de/handle/11303/4219
http://dx.doi.org/10.14279/depositonce-3922
Exam Date: 6-Dec-2013
Issue Date: 24-Jan-2014
Date Available: 24-Jan-2014
DDC Class: 500 Naturwissenschaften und Mathematik
Subject(s): Berechnungsschwere Probleme
Parameterräume
Parametrisierte Algorithmik
Computational hard problems
Parameter spaces
Parameterized algorithms
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
hartung_sepp.pdf2.2 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.