The domatic number problem: Boolean hierarchy completeness and exact exponential time algorithms [Elektronische Ressource] / vorgelegt von Tobias Riege

Sujets

• Informatik
• Mathematics

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2006
• Nombre de lectures: 16
• Langue: English

Extrait

The Domatic Number Problem:
Boolean Hierarchy Completeness and
Exact Exponential-Time Algorithms
Dissertation
zur Erlangung des Doktorgrades der
Mathematisch-Naturwissenschaftlichen Fakult¨at
der Heinrich-Heine-Universit¨at Du¨sseldorf
vorgelegt von
Tobias Riege
geboren in Haltern
Du¨sseldorf, im November 2006Aus dem Institut fu¨r Informatik der
Heinrich-Heine-Universit¨at Du¨sseldorf
Gedruckt mit der Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakult¨at der
Heinrich-Heine-Universit¨at Du¨sseldorf
Referent: Prof. Dr. J¨org Rothe
Koreferent: Prof. Dr. Egon Wanke
Tag der mu¨ndlichen Pru¨fung: 20.12.2006iii
Acknowledgments
I want to thank my thesis advisor J¨org Rothe for all of his support during
the past four years. In the first place, I am deeply gratefulto him forgiving
me the chance to be part of his research team. Without his great efforts,
I would never have had the chance to work in the scientific community.
Many inspiring and valuable discussions with him initiated fruitful ideas
that led to the research presented in this thesis. I am very thankful to him
for letting me have a share of his mathematical precision. In addition, his
profound knowledge of the English language helped a great deal to spice up
our articles.
Next I would like to thank all my coauthors, including J¨org Rothe,
G´abor Erd´elyi, Holger Spakowski, and Masaki Yamamoto. Thanks also to
Gerd Wechsung for pointing out that Exact-2-DNP is coNP-complete and
Dieter Kratsch for giving the hint to Lawler’s algorithm for the colorability
problem.
Many thanks go out to all the great colleagues at the Department of
Computer Science of the Heinrich-Heine-University Du¨sseldorf. For being
the boss: J¨org. For sharing the room with me: G´abor. For countless
cigarettes: Thomas. For all the Mad-Tea-Parties after going to the mensa:
Cristian, Christopher, Johanna, Evgenia, Stefan. Forthetechnical support:
Guido. You all will be missed.
My research was supported by the German Science Foundation (DFG)
under grants RO 1202/9-1 and RO 1202/9-3.
My family always supported me during the last 29 years. Johannes,
Gabriele, Christian, Benjamin, Anna, and Johannes jr.: Thanks for being
there!
Last but not least, I would like to thank Egon Wanke for serving as a
reviewer for this thesis.ivContents
List of Figures vii
List of Tables ix
1 Introduction 1
2 Notations 11
2.1 Sets and Languages . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Machines and Reducibilities . . . . . . . . . . . . . . . . . . 11
2.3 Complexity Classes and Hierarchies . . . . . . . . . . . . . . 15
2.4 Boolean Formulas and Graphs . . . . . . . . . . . . . . . . . 20
2.5 Decision Problems and Their Variants . . . . . . . . . . . . 22
3 The Domatic Number Problem 25
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Exact Version of DNP . . . . . . . . . . . . . . . . . . . . . 27
3.3 The Higher Levels of BH(NP) . . . . . . . . . . . . . . . . . 35
3.4 Harder Questions on Domination . . . . . . . . . . . . . . . 37
4 Generalized Dominating Sets 41
4.1 A General Framework . . . . . . . . . . . . . . . . . . . . . 41
4.2 NP-Completeness Results . . . . . . . . . . . . . . . . . . . 42
4.3 Exact Partitioning Problems . . . . . . . . . . . . . . . . . . 45
+ +4.3.1 The Case σ =N and ρ =N . . . . . . . . . . . . . 46
4.3.2 The Case σ ={0} and ρ =N . . . . . . . . . . . . . 52
+4.3.3 The Cases σ∈{N,N } and ρ =N . . . . . . . . . . 53
4.3.4 The Case σ ={0,1} and ρ =N . . . . . . . . . . . . 53
4.3.5 The Case σ ={1} and ρ =N . . . . . . . . . . . . . 58
4.4 Summary of Results . . . . . . . . . . . . . . . . . . . . . . 59
vvi CONTENTS
5 Exact Exponential-Time Algorithms 61
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Partitioning by Dynamic Programming . . . . . . . . . . . . 64
5.3 Breaking the Trivial Barrier . . . . . . . . . . . . . . . . . . 65
5.4 The Measure & Conquer Technique . . . . . . . . . . . . . . 75
5.5 Improved Result for 3-DNP . . . . . . . . . . . . . . . . . . 77
5.6 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . 80
A Pseudo-Code of the Algorithm 87
Bibliography 91List of Figures
1.1 An example for the coloring problem . . . . . . . . . . . . . 3
2.1 The polynomial hierarchy . . . . . . . . . . . . . . . . . . . 18
2.2 The boolean hierarchy over NP . . . . . . . . . . . . . . . . 20
3.1 Gadget adding domatic numbers of two graphs . . . . . . . . 32
+ +4.1 Graph from reduction to Exact-(3,N ,N )-Partition . . . 49
4.2 Reduction from 1-3-SAT to (2,{0,1},N)-Partition . . . . . 55
4.3 Graph from reduction to Exact-(5,{0,1},N)-Partition . . . 56
A.1 Main body of algorithm for 3-DNP . . . . . . . . . . . . . . . 87
A.2 Recursive function of algorithm for 3-DNP . . . . . . . . . . . 88
A.3 Function to assign vertex v to set D . . . . . . . . . . . . . 88i
A.4 Function to recalculate gaps . . . . . . . . . . . . . . . . . . 89
A.5 Function to handle the critical vertices . . . . . . . . . . . . 90
viiviii LIST OF FIGURESList of Tables
4.1 NP-completeness for (k,σ,ρ)-Partition . . . . . . . . . . . 42
4.2 DP-completeness for Exact-(k,σ,ρ)-Partition. . . . . . . . 60
5.1 Time bounds of algorithms for bounded-degree graphs. . . . 84
ixx LIST OF TABLES