Exact algorithms based on specific complexity measures for hard problems

Mölle, Daniel; Rossmanith, Peter

doi:urn:nbn:de:hbz:82-opus-20722

Exact algorithms based on specific complexity measures for hard problems = Exakte Algorithmen auf der Grundlage problemspezifischer Komplexitätsmaße

Mölle, Daniel (Author)

2007

Verantwortlichkeitsangabevorgelegt von Daniel Mölle

ImpressumAachen : Publikationsserver der RWTH Aachen University 2007

Umfang139 S.

Aachen, Techn. Hochsch., Diss., 2007

Zusammenfassung in engl. und dt. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2007-10-23

Online
URN: urn:nbn:de:hbz:82-opus-20722
URL: https://publications.rwth-aachen.de/record/62539/files/Moelle_Daniel.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Parametrisierte Komplexität (Genormte SW) ; Informatik (frei) ; Exakte Algorithmen (frei) ; Parametrisierte Algorithmen (frei) ; Exact algorithms (frei) ; Parameterized algorithms (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: G.2.2 * G.4 * F.2.0

Kurzfassung
Nach unserem derzeitigen Kenntnisstand erfüllen die meisten wichtigen Probleme der Informatik - seien es Entscheidungs-, Such- oder Optimierungsprobleme - eines der beiden folgenden Kriterien:(1) Das Problem kann relativ zur Eingabelänge n in polynomieller Zeit gelöst werden, wobei der Grad des Polynoms klein genug ist, um auch eine praktische Lösbarkeit des Problems zu garantieren. Insbesondere liegt die Entscheidungsvariante des Problems in P. Typische Zeitkomplexitäten für diesen Fall sind etwa O(n log n) oder O(n^k) mit k < 4.(2) Das Problem ist NP-schwer, und seine Entscheidungsvariante ist NP-vollständig. Wir wissen nicht, ob das Problem in polynomieller Zeit gelöst werden kann, aber es ist ausreichend komplex, um jedes andere NP-vollständige Problem unter Polynomialzeitreduktion ausdrücken zu können. Typische Zeitkomplexitäten für diesen Fall haben die Form O(c^n) mit c > 1.1.Die gemeinhin akzeptierte Hypothese, daß P ungleich NP ist, impliziert, daß exakte Algorithmen für Probleme der zweiten Art zwingend superpolynomielle Laufzeit haben (dies gilt nicht zwangsläufig für jede Eingabe, gleichwohl aber im Worst-Case). Hinsichtlich des Worst-Case-Verhaltens ist somit offensichtlich, daß die entsprechenden Algorithmen schon auf Probleminstanzen moderater Größe unpraktikabel langsam sein können. Die vorliegende Arbeit widmet sich dieser Problematik unter Zuhilfenahme einer Kombination zweier verschiedener Konzepte - eines wohlbekannten Paradigmas und eines bisher nur in weniger expliziter Weise eingesetzten Analysewerkzeugs. Zum einen betrachten wir die parametrisierte Komplexität schwieriger Graphenprobleme. Insbesondere entwerfen und analysieren wir parametrisierte Algorithmen, d.h. Algorithmen, deren Laufzeiten typischerweise exponentiell mit dem jeweiligen Parameter (beispielsweise der gewünschten Größe der Lösung), jedoch lediglich polynomiell mit der Eingabelänge anwachsen. Zum anderen setzen wir problemspezifische Komplexitätsmaße ein: Wir arbeiten mathematische Größen heraus, deren geringe Ausprägung zur effizienteren Lösung des Problems ausgenutzt werden kann, und zeigen dann, daß diese Quantitäten entweder automatisch kleine Werte annehmen oder zumindest mit begrenztem Mehraufwand verkleinert werden können. Derartige Komplexitätsmaße sind aus verschiedenen Gründen nicht mit Parametern zu verwechseln. Allem voran sind die von uns abgeleiteten Laufzeitschranken Funktionen im Parameter k und der Eingabelänge n, nicht aber im jeweiligen Komplexitätsmaß. Weiterhin gebrauchen wir die Begriffe „geringe Ausprägung” und „kleine Werte” in gänzlich verschiedener Weise - für die meisten der oben genannten Probleme untersuchen wir beispielsweise Komplexitätsmaße, die exponentiell groß in k und somit größer als n sein können. Obgleich der Schwerpunkt dieser Arbeit eindeutig auf der theoretischen Seite liegt, ergänzen wir die mathematische Analyse der Algorithmen mit Fallstudien und praktischen Experimenten. In einem Fall exemplifizieren wir, wie ein theoretischer (also ein auf die mathematische Analyse zugeschnittener) Algorithmus implementiert und für eine praktische Anwendung optimiert werden kann.

At present, most of the important computational problems - be they decision, search, or optimization problems - are known to satisfy one of the following two criteria:(1) The problem can be solved in polynomial time with respect to the input size n, where the degree of the polynomial is small enough to guarantee that the problem can be tackled efficiently in practice. In particular, the decision version of the problem is in P. Typical time complexities are O(n log n) and O(n^k), k < 4.(2) The problem is NP-hard, and its decision version is NP-complete. We do not know whether the problem can be solved in polynomial time, but it is complex enough to express every other NP-complete problem via polynomial-time transformations. A typical time complexity for this case is O(c^n) with c > 1.1.Under the widely accepted assumption that P does not equal NP, exact algorithms for problems of the second variety inevitably take superpolynomial time (not necessarily for every input, but in the worst case). In terms of worst-case behavior, it is easy to see that the respective algorithms can be infeasible even for instances of moderate size. The thesis at hand addresses this intricacy by combining two concepts, one of which is a well-known paradigm and the other one of which is an analytical tool that has only been used less explicitly in earlier scholarship. Firstly, we consider the parameterized complexity of hard graph problems. In particular, we design and analyze parameterized algorithms, i.e., algorithms whose running times are typically exponential in some parameter of the input (such as the desired size of the solution), but only polynomial in the size of the input. Secondly, we employ problem-specific complexity measures: we identify quantities whose smallness can be exploited in order to solve the problem more efficiently, then prove that they are small in any case, or that they can be made small using bounded additional effort. Such complexity measures are not to be confused with parameters for several reasons. Most importantly, we derive runtime bounds that are functions in the parameter k and the input size n, not in the complexity measure. The term smallness is also used in varied interpretations - for most of the aforementioned problems, we even investigate complexity measures that can be exponentially large in k and thus greater than n. Although the focus of this thesis clearly lies on the theoretical part, we complement the mathematical analysis of the algorithms with case studies and practical experiments. In one case, we exemplify how a theoretical algorithm (i.e., an algorithm tailored to the mathematical analysis) can be implemented and optimized for use in real-world applications.

Fulltext:
PDF