Invitation to fixed-parameter algorithmsPDF电子书下载

Ⅰ FOUNDATIONS 3

1 Introduction to Fixed-Parameter Algorithms 3

1.1 The satisfiability problem 4

1.2 An example from railway optimization 7

1.3 A communication problem in tree networks 10

1.4 Summary 12

1.5 Exercises 13

1.6 Bibliographical remarks 14

2 Preliminaries and Agreements 17

2.1 Basic sets and problems 17

2.2 Model of computation and running times 17

2.3 Strings and graphs 18

2.4 Complexity and approximation 20

2.5 Bibliographical remarks 21

3 Parameterized Complexity Theory —A Primer 22

3.1 Basic theory 22

3.2 Interpreting fixed-parameter tractability 27

3.3 Exercises 29

3.4 Bibliographical remarks 29

4 Vertex Cover An Illustrative Example 31

4.1 Parameterizing 32

4.2 Specializing 33

4.3 Generalizing 34

4.4 Counting or enumerating 34

4.5 Lower bounds 35

4.6 Implementing and applying 35

4.7 Using vertex cover structure for other problems 36

4.8 Exercises 38

4.9 Bibliographical remarks 38

5 The Art of Problem Parameterization 41

5.1 Parameter really small？ 41

5.2 Guaranteed parameter value？ 42

5.3 More than one obvious parameterization？ 43

5.4 Close to “trivial” problem instances？ 45

5.5 Exercises 47

5.6 Bibliographical remarks 47

6 Summary and Concluding Remarks 49

Ⅱ ALGORITHMIC METHODS 53

7 Data Reduction and Problem Kernels 53

7.1 Basic definitions and facts 55

7.2 Maximum Satisfiability 58

7.3 Cluster Editing 60

7.4 Vertex Cover 64

7.4.1 Kernelization based on matching 64

7.4.2 Kernelization based on linear programming 68

7.4.3 Kernelization based on crown structures 69

7.4.4 Comparison and discussion 72

7.5 3-Hitting Set 72

7.6 Dominating Set in Planar Graphs 74

7.6.1 The neighborhood of a single vertex 74

7.6.2 The neighborhood of a pair of vertices 77

7.6.3 Reduced graphs and the problem kernel 79

7.7 On lower bounds for problem kernels 80

7.8 Summary and concluding remarks 82

7.9 Exercises 83

7.10 Bibliographical remarks 85

8 Depth-Bounded Search Trees 88

8.1 Basic definitions and facts 91

8.2 Cluster Editing 93

8.3 Vertex Cover 98

8.4 Hitting Set 101

8.5 Closest String 103

8.6 Dominating Set in Planar Graphs 107

8.6.1 Data reduction rules 108

8.6.2 Main result and some remarks 109

8.7 Interleaving search trees and kernelization 110

8.7.1 Basic methodology 111

8.7.2 Interleaving is necessary 113

8.8 Automated search tree generation and analysis 114

8.9 Summary and concluding remarks 119

8.10 Exercises 120

8.11 Bibliographical remarks 121

9 Dynamic Programming 124

9.1 Basic definitions and facts 125

9.2 Knapsack 126

9.3 Steiner Problem in Graphs 128

9.4 Multicommodity Demand Flow in Trees 131

9.5 Tree-structured variants of Set Cover 136

9.5.1 Basic definitions and facts 136

9.5.2 Algorithm for Path-like Weighted Set Cover 139

9.5.3 Algorithm for Tree-like Weighted Set Cover 140

9.6 Shrinking search trees 145

9.7 Summary and concluding remarks 146

9.8 Exercises 147

9.9 Bibliographical remarks 148

10 Tree Decompositions of Graphs 150

10.1 Basic definitions and facts 151

10.2 On the construction of tree decompositions 153

10.3 Planar graphs 155

10.4 Dynamic programming for Vertex Cover 160

10.5 Dynamic programming for Dominating Set 164

10.6 Monadic second-order logic （MSO） 169

10.7 Related graph width parameters 172

10.8 Summary and concluding remarks 174

10.9 Exercises 175

10.10Bibliographical remarks 176

11 Further Advanced Techniques 177

11.1 Color-coding 178

11.2 Integer linear programming 181

11.3 Iterative compression 184

11.3.1 Vertex Cover 185

11.3.2 Feedback Vertex Set 187

11.4 Greedy localization 190

11.4.1 Set Splitting 191

11.4.2 Set Packing 193

11.5 Graph minor theory 195

11.6 Summary and concluding remarks 197

11.7 Exercises 198

11.8 Bibliographical remarks 199

12 Summary and Concluding Remarks 201

Ⅲ SOME THEORY，SOME CASE STUDIES 205

13 Parameterized Complexity Theory 205

13.1 Basic definitions and concepts 206

13.1.1 Parameterized reducibility 207

13.1.2 Parameterized complexity classes 209

13.2 The complexity class W[1] 212

13.3 Concrete parameterized reductions 216

13.3.1 W [1]-hardness proofs 218

13.3.2 Further reductions and W[2]-hardness 226

13.4 Some recent developments 230

13.4.1 Lower bounds and the complexity class M[1] 230

13.4.2 Lower bounds and linear FPT reductions 232

13.4.3 Machine models，limited nondeterminism，and bounded FPT 233

13.5 Summary and concluding remarks 234

13.6 Exercises 235

13.7 Bibliographical remarks 235

14 Connections to Approximation Algorithms 237

14.1 Approximation helping parameterization 238

14.2 Parameterization helping approximation 239

14.3 Further （non-）relations 241

14.4 Discussion and concluding remarks 241

14.5 Bibliographical remarks 242

15 Selected Case Studies 243

15.1 Planar and more general graphs 243

15.1.1 Planar graphs 243

15.1.2 More general graphs 245

15.2 Graph modification problems 245

15.2.1 Graph modification and hereditary properties 246

15.2.2 Feedback Vertex Set revisited 247

15.2.3 Graph Bipartization 248

15.2.4 Minimum Fill-In 249

15.2.5 Closest 3-Leaf Power 250

15.3 Miscellaneous graph problems 251

15.3.1 Capacitated Vertex Cover 251

15.3.2 Constraint Bipartite Vertex Cover 253

15.3.3 Graph Coloring 255

15.3.4 Crossing Number 256

15.3.5 Power Dominating Set 257

15.4 Computational biology problems 258

15.4.1 Minimum Quartet Inconsistency 259

15.4.2 Compatibility of Unrooted Phylogenetic Trees 261

15.4.3 Longest Arc-Preserving Common Subsequences 262

15.4.4 Incomplete Perfect Path Phylogeny Haplotyp-ing 264

15.5 Logic and related problems 266

15.5.1 Satisfiability 266

15.5.2 Maximum Satisfiability 268

15.5.3 Constraint satisfaction problems 269

15.5.4 Database queries 270

15.6 Miscellaneous problems 271

15.6.1 Two-dimensional Euclidean TSP 272

15.6.2 Multidimensional matching 273

15.6.3 Matrix Domination 273

15.6.4 Vapnik-Chervonenkis Dimension 274

15.7 Summary and concluding remarks 275

16 Zukunftsmusik 277

References 279

Index 294