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

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

English
109 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

The Domatic Number Problem:Boolean Hierarchy Completeness andExact Exponential-Time AlgorithmsDissertationzur Erlangung des Doktorgrades derMathematisch-Naturwissenschaftlichen Fakult¨atder Heinrich-Heine-Universit¨at Du¨sseldorfvorgelegt vonTobias Riegegeboren in HalternDu¨sseldorf, im November 2006Aus dem Institut fu¨r Informatik derHeinrich-Heine-Universit¨at Du¨sseldorfGedruckt mit der Genehmigung derMathematisch-Naturwissenschaftlichen Fakult¨at derHeinrich-Heine-Universit¨at Du¨sseldorfReferent: Prof. Dr. J¨org RotheKoreferent: Prof. Dr. Egon WankeTag der mu¨ndlichen Pru¨fung: 20.12.2006iiiAcknowledgmentsI want to thank my thesis advisor J¨org Rothe for all of his support duringthe past four years. In the first place, I am deeply gratefulto him forgivingme 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 ideasthat led to the research presented in this thesis. I am very thankful to himfor letting me have a share of his mathematical precision. In addition, hisprofound knowledge of the English language helped a great deal to spice upour articles.Next I would like to thank all my coauthors, including J¨org Rothe,G´abor Erd´elyi, Holger Spakowski, and Masaki Yamamoto.

Subjects

Informations

Published by
Published 01 January 2006
Reads 16
Language English
Report a problem

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