Exact algorithms based on specific complexity measures for hard problems [Elektronische Ressource] / vorgelegt von Daniel Mölle

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 12
• Langue: English

Extrait

Exact Algorithms
Based on Speci c Complexity Measures
for Hard Problems
Von der Fakultat fur Mathematik, Informatik und Naturwissenschaften der
Rheinisch-Westfalischen Technischen Hochschule Aachen zur Erlangung
des akademischen Grades eines Doktors derhaften
genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Daniel Molle
aus Essen
Berichter: Universitatsprofessor Dr. rer. nat. Peter Rossmanith
Universit Dr. Fedor V. Fomin (University of Bergen)
Tag der mundlic hen Prufung: 23.10.2007
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.iii
Abstract
At present, most of the important computational problems|be they de-
cision, 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 e cien tly in practice. In
particular, the decision version of the problem is in P. Typical time
kcomplexities are O(nlog n) and O(n ), k 3.
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
nthis case is O(c ) with c > 1:1.
Under the widely accepted assumption that P=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 prob-
lems. 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. The most important of the resulting runtime bounds
are:
kO((2 + ") poly(n)) to nd an optimum Steiner tree for k terminals
kO(2:7606 poly(n)) to check for a k-node connected vertex cover
kO(3:2361 poly(n)) to check for a k-node tree cover of weight W
kO(1:3803 poly(n)) to count all vertex covers of size up to k
kO(4 poly(n)) to check for a k-node path
kO((16 + ") poly(n)) to check for k edge-disjoint triangles
All of the above results constitute the best parameterized runtime bounds
for the respective problems known today.
Secondly, we employ problem-speci c complexity measures: we identify
quantities whose smallness can be exploited in order to solve the problem
more e cien tly, then prove that they are small in any case, or that they can
be made small using bounded additional e ort. Such complexity measures
6iv
are not to be confused with parameters for several reasons. Most impor-
tantly, 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.v
Zusammenfassung
Nach unserem derzeitigen Kenntnisstand erfullen die meisten wichtigen Pro-
bleme der Informatik { seien es Entscheidungs-, Such- oder Optimierungs-
probleme { eines der beiden folgenden Kriterien:
1. Das Problem kann relativ zur Eingabelange n in polynomieller Zeit
gelost werden, wobei der Grad des Polynoms klein genug ist, um auch
eine praktische Losbarkeit des Problems zu garantieren. Insbesondere
liegt die Entscheidungsvariante des Problems in P. Typische Zeitkom-
kplexitaten fur diesen Fall sind etwa O(nlog n) oder O(n ) mit k 3.
2. Das Problem ist NP-schwer, und seine Entscheidungsvariante ist NP-
vollstandig. Wir wissen nicht, ob das Problem in polynomieller Zeit
gelost werden kann, aber es ist ausreichend komplex, um jedes andere
NP-vollstandige Problem unter Polynomialzeitreduktion ausdruc ken
zu konnen. Typische Zeitkomplexitaten fur diesen Fall haben die Form
nO(c ) mit c > 1:1.
Die gemeinhin akzeptierte Hypothese P=NP impliziert, da exakte Algo-
rithmen fur Probleme der zweiten Art zwingend superpolynomielle Lauf-
zeit haben (dies gilt nicht zwangslau g fur jede Eingabe, gleichwohl aber im
Worst-Case). Hinsichtlich des Worst-Case-Verhaltens ist somit o ensic htlich,
da die entsprechenden Algorithmen schon auf Probleminstanzen moderater
Gro e unpraktikabel langsam sein konnen.
Die vorliegende Arbeit widmet sich dieser Problematik unter Zuhilfenah-
me einer Kombination zweier verschiedener Konzepte { eines wohlbekannten
Paradigmas und eines bisher nur in weniger expliziter Weise eingesetzten
Analysewerkzeugs.
Zum einen betrachten wir die parametrisierte Komplexitat schwieriger
Graphenprobleme. Insbesondere entwerfen und analysieren wir parametri-
sierte Algorithmen, d.h. Algorithmen, deren Laufzeiten typischerweise ex-
ponentiell mit dem jeweiligen Parameter (beispielsweise der gewunsc hten
Gro e der Losung), jedoch lediglich polynomiell mit der Eingabelange an-
wachsen. Die wichtigsten der hieraus resultierenden Laufzeitschranken zur
Berechnung beziehungsweise Erkennung der jeweils genannten Entitaten lau-
ten:
kO((2 + ") poly(n)) optimaler Steinerbaum fur k Terminals
kO(2:7606 poly(n)) zusammenhangendes Vertex Cover mit k Knoten
kO(3:2361 poly(n)) gewichtsbeschranktes Tree Cover mit k
kO(1:3803 poly(n)) Anzahl der Vertex Cover der Gro e hochstens k
kO(4 poly(n)) Pfad mit k Knoten
kO((16 + ") poly(n)) k kantendisjunkte Dreiecke
Die hier aufgefuhrten Ergebnisse stellen die derzeit besten parametrisierten
Laufzeitschranken fur die jeweiligen Probleme dar.
6vi
Zum anderen setzen wir problemspezi sc he Komplexitatsma e ein: Wir
arbeiten mathematische Gro en heraus, deren geringe Auspragung zur e -
zienteren Losung des Problems ausgenutzt werden kann, und zeigen dann,
da diese Quantitaten entweder automatisch kleine Werte annehmen oder
zumindest mit begrenztem Mehraufwand verkleinert werden konnen. Der-
artige Komplexitatsma e sind aus verschiedenen Grunden nicht mit Para-
metern zu verwechseln. Allem voran sind die von uns abgeleiteten Laufzeit-
schranken Funktionen im Parameter k und der Eingabelange n, nicht aber
im jeweiligen Komplexitatsma . Weiterhin gebrauchen wir die Begri e ge-
"
ringe Auspragung\ und kleine Werte\ in ganzlich verschiedener Weise {
"
fur die meisten der oben genannten Probleme untersuchen wir beispielswei-
se Komplexitatsma e, die exponentiell gro in k und somit gro er als n sein
konnen.
Obgleich der Schwerpunkt dieser Arbeit eindeutig auf der theoretischen
Seite liegt, erganzen wir die mathematische Analyse der Algorithmen mit
Fallstudien und praktischen Experimenten. In einem Fall exempli zieren
wir, wie ein theoretischer (also ein auf die mathematische Analyse zuge-
schnittener) Algorithmus implementiert und fur eine praktische Anwendung
optimiert werden kann.vii
Acknowledgements
This thesis would not have come into existence but for the in uence and
support of the following individuals and organizations, to whom I wish to
express my heartfelt gratitude:
I am deeply grateful to Peter Rossmanith, an advisor who never ceases to
supply his Ph.D. students with amazing ideas, exciting challenges, and wise
counsel. He fought hard to keep me as a research assistant while the funding
was in question and taught me countless useful lessons regarding as diverse
issues as the analysis of algorithms, green tea, METAPOST, parameterized
complexity, persistence, soldering, typesetting, and Z80 appreciation.
I would also like to thank Fedor Fomin for acting as a second referee and
taking the time to come to Aachen for my Ph.D. exam.
Similarly, I feel most indebted to the German Research Foundation
(Deutsche Forschungsgemeinschaft). By funding the project RO 927/6, they
allowed me to participate in most exciting research and conferences.
My sincere thanks also go to my fellow Ph.D. students Joachim Kneis and
Stefan Richter who have always been gladly available for fruitful discussions
and productive paper-writing frenzies.
I would like to extend my gratitude towards Beate Bollig, Stefan Droste,
Thomas Hofmeister, Detlef Sieling, and Ingo Wegener of the Lehrstuhl In-
formatik 2 at the University of Dortmund. Their excellent teaching and
supervision ignited my passion for theoretical computer science, converting
an interested student into an excited enthusiast.
Many thanks also go to Peter Padawitz, n