A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research.
Author(s): Rolf Niedermeier
Series: Oxford Lecture Series in Mathematics and Its Applications
Publisher: Oxford University Press, USA
Year: 2006
Language: English
Pages: 313
0198566077......Page 1
Contents......Page 8
I: FOUNDATIONS......Page 14
1 Introduction to Fixed-Parameter Algorithms......Page 16
1.1 The satisfiability problem......Page 17
1.2 An example from railway optimization......Page 20
1.3 A communication problem in tree networks......Page 23
1.4 Summary......Page 25
1.5 Exercises......Page 26
1.6 Bibliographical remarks......Page 27
2.2 Model of computation and running times......Page 30
2.3 Strings and graphs......Page 31
2.4 Complexity and approximation......Page 33
2.5 Bibliographical remarks......Page 34
3.1 Basic theory......Page 35
3.2 Interpreting fixed-parameter tractability......Page 40
3.4 Bibliographical remarks......Page 42
4 Vertex Cover—An Illustrative Example......Page 44
4.1 Parameterizing......Page 45
4.2 Specializing......Page 46
4.4 Counting or enumerating......Page 47
4.6 Implementing and applying......Page 48
4.7 Using vertex cover structure for other problems......Page 49
4.9 Bibliographical remarks......Page 51
5.1 Parameter really small?......Page 54
5.2 Guaranteed parameter value?......Page 55
5.3 More than one obvious parameterization?......Page 56
5.4 Close to “trivial” problem instances?......Page 58
5.6 Bibliographical remarks......Page 60
6 Summary and Concluding Remarks......Page 62
II: ALGORITHMIC METHODS......Page 64
7 Data Reduction and Problem Kernels......Page 66
7.1 Basic definitions and facts......Page 68
7.2 Maximum Satisfiability......Page 71
7.3 Cluster Editing......Page 73
7.4 Vertex Cover......Page 77
7.5 3-Hitting Set......Page 85
7.6 Dominating Set in Planar Graphs......Page 87
7.7 On lower bounds for problem kernels......Page 93
7.8 Summary and concluding remarks......Page 95
7.9 Exercises......Page 96
7.10 Bibliographical remarks......Page 98
8 Depth-Bounded Search Trees......Page 101
8.1 Basic definitions and facts......Page 104
8.2 Cluster Editing......Page 106
8.3 Vertex Cover......Page 111
8.4 Hitting Set......Page 114
8.5 Closest String......Page 116
8.6 Dominating Set in Planar Graphs......Page 120
8.7 Interleaving search trees and kernelization......Page 123
8.8 Automated search tree generation and analysis......Page 127
8.9 Summary and concluding remarks......Page 132
8.10 Exercises......Page 133
8.11 Bibliographical remarks......Page 134
9 Dynamic Programming......Page 137
9.1 Basic definitions and facts......Page 138
9.2 Knapsack......Page 139
9.3 Steiner Problem in Graphs......Page 141
9.4 Multicommodity Demand Flow in Trees......Page 144
9.5 Tree-structured variants of Set Cover......Page 149
9.6 Shrinking search trees......Page 158
9.7 Summary and concluding remarks......Page 159
9.8 Exercises......Page 160
9.9 Bibliographical remarks......Page 161
10 Tree Decompositions of Graphs......Page 163
10.1 Basic definitions and facts......Page 164
10.2 On the construction of tree decompositions......Page 166
10.3 Planar graphs......Page 168
10.4 Dynamic programming for Vertex Cover......Page 173
10.5 Dynamic programming for Dominating Set......Page 177
10.6 Monadic second-order logic (MSO)......Page 182
10.7 Related graph width parameters......Page 185
10.8 Summary and concluding remarks......Page 187
10.9 Exercises......Page 188
10.10 Bibliographical remarks......Page 189
11 Further Advanced Techniques......Page 190
11.1 Color-coding......Page 191
11.2 Integer linear programming......Page 194
11.3 Iterative compression......Page 197
11.4 Greedy localization......Page 203
11.5 Graph minor theory......Page 208
11.6 Summary and concluding remarks......Page 210
11.7 Exercises......Page 211
11.8 Bibliographical remarks......Page 212
12 Summary and Concluding Remarks......Page 214
III: SOME THEORY, SOME CASE STUDIES......Page 216
13 Parameterized Complexity Theory......Page 218
13.1 Basic definitions and concepts......Page 219
13.2 The complexity class W[1]......Page 225
13.3 Concrete parameterized reductions......Page 229
13.4 Some recent developments......Page 243
13.5 Summary and concluding remarks......Page 247
13.7 Bibliographical remarks......Page 248
14 Connections to Approximation Algorithms......Page 250
14.1 Approximation helping parameterization......Page 251
14.2 Parameterization helping approximation......Page 252
14.4 Discussion and concluding remarks......Page 254
14.5 Bibliographical remarks......Page 255
15.1 Planar and more general graphs......Page 256
15.2 Graph modification problems......Page 258
15.3 Miscellaneous graph problems......Page 264
15.4 Computational biology problems......Page 271
15.5 Logic and related problems......Page 279
15.6 Miscellaneous problems......Page 284
15.7 Summary and concluding remarks......Page 288
16 Zukunftsmusik......Page 290
References......Page 292
C......Page 307
F......Page 308
H......Page 309
N......Page 310
P......Page 311
S......Page 312
Z......Page 313
