Invitation to fixed-parameter algorithmsPDF|Epub|txt|kindle电子书版本网盘下载

Invitation to fixed-parameter algorithmsPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Ⅰ FOUNDATIONS3

1 Introduction to Fixed-Parameter Algorithms3

1.1 The satisfiability problem4

1.2 An example from railway optimization7

1.3 A communication problem in tree networks10

1.4 Summary12

1.5 Exercises13

1.6 Bibliographical remarks14

2 Preliminaries and Agreements17

2.1 Basic sets and problems17

2.2 Model of computation and running times17

2.3 Strings and graphs18

2.4 Complexity and approximation20

2.5 Bibliographical remarks21

3 Parameterized Complexity Theory —A Primer22

3.1 Basic theory22

3.2 Interpreting fixed-parameter tractability27

3.3 Exercises29

3.4 Bibliographical remarks29

4 Vertex Cover An Illustrative Example31

4.1 Parameterizing32

4.2 Specializing33

4.3 Generalizing34

4.4 Counting or enumerating34

4.5 Lower bounds35

4.6 Implementing and applying35

4.7 Using vertex cover structure for other problems36

4.8 Exercises38

4.9 Bibliographical remarks38

5 The Art of Problem Parameterization41

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 Exercises47

5.6 Bibliographical remarks47

6 Summary and Concluding Remarks49

Ⅱ ALGORITHMIC METHODS53

7 Data Reduction and Problem Kernels53

7.1 Basic definitions and facts55

7.2 Maximum Satisfiability58

7.3 Cluster Editing60

7.4 Vertex Cover64

7.4.1 Kernelization based on matching64

7.4.2 Kernelization based on linear programming68

7.4.3 Kernelization based on crown structures69

7.4.4 Comparison and discussion72

7.5 3-Hitting Set72

7.6 Dominating Set in Planar Graphs74

7.6.1 The neighborhood of a single vertex74

7.6.2 The neighborhood of a pair of vertices77

7.6.3 Reduced graphs and the problem kernel79

7.7 On lower bounds for problem kernels80

7.8 Summary and concluding remarks82

7.9 Exercises83

7.10 Bibliographical remarks85

8 Depth-Bounded Search Trees88

8.1 Basic definitions and facts91

8.2 Cluster Editing93

8.3 Vertex Cover98

8.4 Hitting Set101

8.5 Closest String103

8.6 Dominating Set in Planar Graphs107

8.6.1 Data reduction rules108

8.6.2 Main result and some remarks109

8.7 Interleaving search trees and kernelization110

8.7.1 Basic methodology111

8.7.2 Interleaving is necessary113

8.8 Automated search tree generation and analysis114

8.9 Summary and concluding remarks119

8.10 Exercises120

8.11 Bibliographical remarks121

9 Dynamic Programming124

9.1 Basic definitions and facts125

9.2 Knapsack126

9.3 Steiner Problem in Graphs128

9.4 Multicommodity Demand Flow in Trees131

9.5 Tree-structured variants of Set Cover136

9.5.1 Basic definitions and facts136

9.5.2 Algorithm for Path-like Weighted Set Cover139

9.5.3 Algorithm for Tree-like Weighted Set Cover140

9.6 Shrinking search trees145

9.7 Summary and concluding remarks146

9.8 Exercises147

9.9 Bibliographical remarks148

10 Tree Decompositions of Graphs150

10.1 Basic definitions and facts151

10.2 On the construction of tree decompositions153

10.3 Planar graphs155

10.4 Dynamic programming for Vertex Cover160

10.5 Dynamic programming for Dominating Set164

10.6 Monadic second-order logic （MSO）169

10.7 Related graph width parameters172

10.8 Summary and concluding remarks174

10.9 Exercises175

10.10Bibliographical remarks176

11 Further Advanced Techniques177

11.1 Color-coding178

11.2 Integer linear programming181

11.3 Iterative compression184

11.3.1 Vertex Cover185

11.3.2 Feedback Vertex Set187

11.4 Greedy localization190

11.4.1 Set Splitting191

11.4.2 Set Packing193

11.5 Graph minor theory195

11.6 Summary and concluding remarks197

11.7 Exercises198

11.8 Bibliographical remarks199

12 Summary and Concluding Remarks201

Ⅲ SOME THEORY，SOME CASE STUDIES205

13 Parameterized Complexity Theory205

13.1 Basic definitions and concepts206

13.1.1 Parameterized reducibility207

13.1.2 Parameterized complexity classes209

13.2 The complexity class W[1]212

13.3 Concrete parameterized reductions216

13.3.1 W [1]-hardness proofs218

13.3.2 Further reductions and W[2]-hardness226

13.4 Some recent developments230

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

13.4.2 Lower bounds and linear FPT reductions232

13.4.3 Machine models，limited nondeterminism，and bounded FPT233

13.5 Summary and concluding remarks234

13.6 Exercises235

13.7 Bibliographical remarks235

14 Connections to Approximation Algorithms237

14.1 Approximation helping parameterization238

14.2 Parameterization helping approximation239

14.3 Further （non-）relations241

14.4 Discussion and concluding remarks241

14.5 Bibliographical remarks242

15 Selected Case Studies243

15.1 Planar and more general graphs243

15.1.1 Planar graphs243

15.1.2 More general graphs245

15.2 Graph modification problems245

15.2.1 Graph modification and hereditary properties246

15.2.2 Feedback Vertex Set revisited247

15.2.3 Graph Bipartization248

15.2.4 Minimum Fill-In249

15.2.5 Closest 3-Leaf Power250

15.3 Miscellaneous graph problems251

15.3.1 Capacitated Vertex Cover251

15.3.2 Constraint Bipartite Vertex Cover253

15.3.3 Graph Coloring255

15.3.4 Crossing Number256

15.3.5 Power Dominating Set257

15.4 Computational biology problems258

15.4.1 Minimum Quartet Inconsistency259

15.4.2 Compatibility of Unrooted Phylogenetic Trees261

15.4.3 Longest Arc-Preserving Common Subsequences262

15.4.4 Incomplete Perfect Path Phylogeny Haplotyp-ing264

15.5 Logic and related problems266

15.5.1 Satisfiability266

15.5.2 Maximum Satisfiability268

15.5.3 Constraint satisfaction problems269

15.5.4 Database queries270

15.6 Miscellaneous problems271

15.6.1 Two-dimensional Euclidean TSP272

15.6.2 Multidimensional matching273

15.6.3 Matrix Domination273

15.6.4 Vapnik-Chervonenkis Dimension274

15.7 Summary and concluding remarks275

16 Zukunftsmusik277

References279

Index294