Intuitive algorithms [Elektronische Ressource] / vorgelegt von Joachim Kneis

Description

Intuitive AlgorithmsVonderFakultatfurMathematik,InformatikundNaturwissenschaftenderRWTHAachen University zur Erlangung des akademischen Grades eines Doktors derNaturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerJoachim Kneisaus KolnBerichter: Prof. Dr. Peter RossmanithProf. Dr. Dieter KratschTag der mundlichen Prufung: 23.7.2009DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfugbar.ii6AbstractAssuming P = NP, which is widely believed to be true, many important com-putational problems are not solvable in polynomial time. However, this does notimply that NP-hard problems are not exactly solvable at all. Both the conceptsof moderately exponential time algorithms and parameterized complexity providetools for solving many of these problems in reasonable time.In this thesis, we introduce the concept of intuitive algorithms. While intuitivealgorithmscanbeeithermoderatelyexponential timealgorithmsorparameterizedalgorithms, we require that they follow an intuitive idea and are kept as simple aspossible.When we analyze algorithms only in terms of a worst case runtime bound, thisapproachisdisadvantageous, asitissometimes muchhardertoprovegoodboundsfor simpler algorithms. In some cases, this might even be impossible. However,we will show that there are several aspects of intuitive algorithms that makes thedevelopment of such algorithms worthwhile.For example, their runtime is often not as bad as assumed.

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2009
• Nombre de lectures: 9
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Intuitive Algorithms
VonderFakultatfurMathematik,InformatikundNaturwissenschaftenderRWTH
Aachen University zur Erlangung des akademischen Grades eines Doktors der
Naturwissenschaften genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Joachim Kneis
aus Koln
Berichter: Prof. Dr. Peter Rossmanith
Prof. Dr. Dieter Kratsch
Tag der mundlichen Prufung: 23.7.2009
DieseDissertationistaufdenInternetseitenderHochschulbibliothekonlineverfugbar.iiAbstract
Assuming P = NP, which is widely believed to be true, many important com-
putational problems are not solvable in polynomial time. However, this does not
imply that NP-hard problems are not exactly solvable at all. Both the concepts
of moderately exponential time algorithms and parameterized complexity provide
tools for solving many of these problems in reasonable time.
In this thesis, we introduce the concept of intuitive algorithms. While intuitive
algorithmscanbeeithermoderatelyexponential timealgorithmsorparameterized
algorithms, we require that they follow an intuitive idea and are kept as simple as
possible.
When we analyze algorithms only in terms of a worst case runtime bound, this
approachisdisadvantageous, asitissometimes muchhardertoprovegoodbounds
for simpler algorithms. In some cases, this might even be impossible. However,
we will show that there are several aspects of intuitive algorithms that makes the
development of such algorithms worthwhile.
For example, their runtime is often not as bad as assumed. Especially on small
instances, intuitivealgorithmsoftenoutperformmorecomplexalgorithms,because
the more complex algorithms tend to unfold their full potential on large instances.
However, in practice large instances cannot be solved with exponential time al-
gorithms at all. Furthermore, we often do to not know precise lower bounds on
the runtime of exact algorithms. Is is thus hard to decide, whether more complex
operations only ease the analysis of a complex algorithm or if such operations re-
ally improve the running time. Moreover, intuitive algorithms tend to allow for
efficient implementations. This allows us to solve real life instances of surpris-
ingly large size. In contrast tothis, implementations ofcomplex algorithms canbe
rather slow. Finally, intuitive algorithms are often more aesthetic than complex
algorithms. Overall, simpler algorithms often tell us more about problems.
Throughout this thesis, we will outline that intuitive algorithms can also be
competitive when compared to traditional algorithms. To emphasize this, we will
present several examples of intuitive algorithms that are either the fastest known
algorithms or have only been improved recently.
List of Results
• ForMax-2SAT andMax-Cut, we present intuitive algorithms with a run-
∗ mtime bounded by O (1.128 ), where m denotes the number of clauses or
edges, respectively.
• For the Maximum Leaf Spanning Tree problem, we introduce an in-
∗ ktuitive algorithm with a runtime bounded by O (4 ) that works both on
iii
6undirected and directed graphs. Here, the parameter k denotes the number
of leaves.
• WeshowthatPartialVertexCovercanbesolvedwithandeterministic
∗ tintuitive algorithm in time O (1.396 ) and with a less intuitive randomized
∗ talgorithm in time O (1.2993 ), where t is the number of covered edges.
• Moreover, we present an algorithm for Partial Dominating Set with
∗ ta runtime bounded by O ((4 + ε) ), which is based on the technique of
Divide & Color. Here t denotes the number of dominated nodes.
• Finally, we present an intuitive algorithm for Independent Set with a
∗ |V|runtime bounded by O (1.2132 ).
Thefirstandthelastresulttherebyaremoderatelyexponentialtimealgorithms,
while our algorithms for Maximum Leaf Spanning Tree, Partial Vertex
Cover,andPartialDominatingSetareparameterizedalgorithms. Thefocus
in this thesis lies on proving the claimed theoretical runtime bounds for these
algorithms. However, we will also present implementations for each algorithm and
argue that they can be used to solve surprisingly large instances.
ivAcknowledgments
My first and sincere thanks go to my supervisor Professor Peter Rossmanith for
his wise guidance, his unstoppable enthusiasm fornew ideas, his deep insights into
algorithms and complexity as well as his valuable advice on exotic food. Without
his foresight, patience and trust in me, I might not have come to this point.
Furthermore, my warmest thanks go to all the members (former and present) of
the Lehr- und Forschungsgebiet Theoretische Informatik at RWTH Aachen Uni-
versity, forsharingideasandagreatworkingatmosphere: DanielMolle,Alexander
Langer and Stefan Richter. Working together with them was both entertaining
and enlightening.
Many thanks for the invitation to ETH Zurich and the hospitality to Professor
Juraj Hromkovic and my other co-workers atthe Chair of Information Technology
and Education: Hans-Joachim Bockenhauer and Joachim Kupke.
Moreover, I would like to thank all of my co-authors (in alphabetical order):
Hans-Joachim Bockenhauer, Henning Fernau, Luca Forlizzi, Jens Gerlach, Ju-
raj Hromkovic, Joachim Kupke, Dieter Kratsch, Daniel Molle, Alexander Langer,
MathieuLiedloff,GuidoProietti,DanielRaible,StefanRichter,PeterRossmanith,
and Peter Widmayer for sharing their knowledge and expertise with me. They all
greatly contributed to the successful completion of this dissertation.
Last but not least, I want to thank my parents and my wife Anne for their
support and help throughout all these years.
This thesis was funded by the German Research Foundation (DFG) under the
project RO 927/7.
vviContents
1 Introduction 1
1.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Intuitive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 MaxCut and Max2SAT 9
2.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 A Confluent Set of Reduction Rules . . . . . . . . . . . . . . . . . . 12
2.3 Bounds on Treewidth and Pathwidth . . . . . . . . . . . . . . . . . 19
2.4 A General Framework for Intuitive Algorithms . . . . . . . . . . . . 26
2.4.1 Algorithms forMax-2SAT and Max-Cut . . . . . . . . . 31
2.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3 Maximum Leaf Trees 45
3.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4 Partial Vertex Cover 65
4.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3 A Fast Algorithm on Cubic Graphs . . . . . . . . . . . . . . . . . . 70
4.4 A deterministic algorithm . . . . . . . . . . . . . . . . . . . . . . . 76
4.5 A randomized algorithm . . . . . . . . . . . . . . . . . . . . . . . . 78
4.6 Exact Partial Vertex Cover . . . . . . . . . . . . . . . . . . 83
4.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5 Partial Dominating Set 91
5.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 A Problem Kernel forPartial Dominating Set . . . . . . . . . 92
viiContents
5.3 A Randomized Algorithm forPartial Dominating Set . . . . . 94
5.4 Derandomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Independent Set 107
6.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.2 An Intuitive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3 Sparse Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3.1 Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . . . 117
6.4 Arbitrary Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.5 A Computer Aided Case Distinction . . . . . . . . . . . . . . . . . 128
6.5.1 A General Framework for Computer Aided Proofs . . . . . . 128
6.5.2 Generating all Graphlets of maximum Degree Four . . . . . 129
6.6 A Traditional Analysis of the Remaining Cases . . . . . . . . . . . . 135
6.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7 Conclusion 147
Bibliography 149
A Tree- and Pathwidth: Basic Definitions 161
B Implementation Details 163
B.1 Maximum Leaf Spanning Tree . . . . . . . . . . . . . . . . . . . . . 163
B.2 Partial Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . 165
B.3 Independent Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
viii1 Introduction
One of the fundamental concepts in computer science is the classification of