Treewidth, kernels, and algorithms. Dedicated to Hans L. Bodlaender - 60

Preface......Page 7
Laudations......Page 9
Seeing Arboretum for the (partial k-) Trees......Page 10
Hans Bodlaender and the Theory of Kernelization Lower Bounds......Page 11
Intelligent Cards for Excellent People......Page 12
Contents......Page 14
About the Jubilee......Page 16
Short Contributions......Page 55
Seeing Arboretum for the (partial k-) Trees......Page 56
 References......Page 58
 1 Introduction......Page 60
 3 Win/Wins......Page 61
 4 Too Much Information Compression!......Page 62
 5 The Functor Project......Page 64
 6 Conclusion......Page 69
 References......Page 70
 1 Age of Exploration......Page 71
 2 Technological Breakthrough......Page 72
 5 The World We Live in Today......Page 73
 References......Page 74
Algorithms, Complexity, and Hans......Page 75
 References......Page 79
Surveys......Page 81
 1 Introduction......Page 82
 2 Non-similarly Sized Fat Objects......Page 85
 3 A Lower Bound for Dominating Set in Ball Graphs......Page 87
 4 A Lower Bound for Weighted Dominating Set in Unit-Ball Graphs......Page 93
 5 Concluding Remarks......Page 97
 References......Page 98
 1 Introduction......Page 100
  2.1 Static Graphs and Treewidth......Page 103
  2.3 Parameterized Complexity......Page 105
 3 Intractability for Constant Underlying Treewidth......Page 106
  3.1 Temporal Exploration......Page 107
  3.2 Temporal Reachability......Page 108
  3.3 Temporal Matching......Page 110
 4 Dynamic Programming Based on an Underlying Tree Decomposition......Page 111
  4.1 Two XP-Algorithms......Page 112
  4.2 Two Fixed-Parameter Polynomial-Time Algorithms......Page 114
 5 Monadic Second-Order Logic for Temporal Graphs......Page 115
  5.2 Enriching the Vocabulary......Page 116
  5.3 Pitfalls in the Literature......Page 117
 6 Possible Definitions of Temporal Treewidth......Page 119
  6.1 Adaptions of the Tree Decomposition......Page 120
  6.2 Treewidth of the Static Expansion......Page 122
 7 Conclusion......Page 123
 A  Temporal Graph Problem Zoo......Page 124
 References......Page 125
 1 Introduction......Page 129
 2 An Interval Representation of Pathwidth......Page 130
 3 Perfect Elimination Ordering......Page 132
 4 Tree Drawing Formulation......Page 134
 5 Set Partitioning Formulation......Page 136
 References......Page 138
  1.1 Our Meeting......Page 140
  1.2 Our Work on Kernelization Lower Bounds......Page 141
  2.1 Kernelization......Page 142
  2.2 Intuition for Polynomial Kernelization Lower Bounds......Page 143
  2.3 The Formal Cross-Composition Framework......Page 145
 3 Vertex Cover......Page 147
 4 Feedback Vertex Set......Page 150
 5 H-Factor......Page 152
 6 Conclusion......Page 159
 References......Page 160
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths......Page 163
 1 Background on Graph Minors Theory with Emphasis on Efficiency......Page 164
  2.1 Minor Testing and Disjoint Paths on Planar Graphs......Page 167
  2.2 General Structure of Algorithms for (Planar) Disjoint Paths......Page 168
  3.1 Schrijver's Main Technical Result......Page 170
  3.2 Key Player: Steiner Tree......Page 173
 References......Page 175
 1 Introduction......Page 180
 2 Bidimensionality......Page 181
 3 Exponential-Time Algorithms for Graphs of Maximum Degree 3......Page 183
 4 Finding and Counting Permutation Patterns......Page 184
 5 Counting Subgraphs......Page 187
 References......Page 191
 1 Introduction......Page 196
 2 Preliminaries......Page 197
  3.1 Some Rank-Related Parameters of Matrices......Page 198
  3.2 Field Rank: Partitions and Matchings......Page 200
  3.3 Boolean Rank: Disjointness Matrix......Page 202
  3.4 Support Rank: Linear Independence and Bipartite Colorings......Page 203
 4 Using Low Rank Matrix Factorizations to Speed up Dynamic Programming......Page 205
  4.1 Cutwidth......Page 206
  4.2 Pathwidth......Page 207
  4.3 k-Path......Page 210
  5.1 Pair Problems......Page 211
  5.3 Counting Algorithms......Page 212
 References......Page 213
 1 Introduction......Page 216
  2.1 Extremal Cases......Page 217
  2.2 Graph Classes......Page 218
  2.3 Parameterized Complexity......Page 219
  2.4 Approximation......Page 220
 References......Page 221
 1 Introduction......Page 224
 2 Scattered Set and Voronoi Diagrams......Page 225
 3 Geometric Halfspace Cover and Uncovered Polytope......Page 229
 4 Steiner Tree and a Local Search Optimum......Page 233
 References......Page 238
 1 Introduction......Page 240
  2.1 Balanced Separators and Well-Linked Sets......Page 243
  2.2 Recursive Construction of a Decomposition......Page 246
  2.3 Futher Reading......Page 248
  3.1 Gathering Ideas......Page 250
  3.2 Recursive Instance Reduction......Page 253
  3.3 Treewidth over Treewidth: The Bodlaender-Kloks Algorithm......Page 256
 References......Page 262
 1 My Personal History in Treewidth Research and the Influence of Hans......Page 265
 2 Feasible Sets: General Versus Connected......Page 266
 3 Minimal Separators and Potential Maximal Cliques......Page 268
 4 Conclusions......Page 270
 References......Page 271
 1 Introduction......Page 273
  2.1 Parameterized Problems on Graphs......Page 275
  2.3 Graph Decompositions......Page 277
  2.4 Boundaried Graphs......Page 278
  3.1 Meta-kernels for Subset Properties with Finite Index......Page 279
  3.2 Meta-kernels for Subset Properties with Finite Integer Index......Page 285
  4.1 Counting Monadic Second Order Logic......Page 286
  4.2 Properties of Defining Pairs......Page 288
  4.3 Theorems on Properties of Defining Pairs......Page 290
  4.4 Applications......Page 291
 References......Page 292
 1 Introduction......Page 298
  2.1 NP-Hard Video Games......Page 300
  2.2 PSPACE-Hard Video Games......Page 301
 3 Constraint Logic Framework......Page 304
 4 Partition and Packing Problems......Page 307
 References......Page 311
 1 Introduction......Page 313
  2.1 Graphs and Tree Decompositions......Page 315
  2.2 Dynamic Programming for [,]-Domination Problems......Page 317
  3.1 The Discrete Fourier Transforms Using Modular Arithmetic......Page 322
  3.2 Möbius Inversion Using Fast Zeta and Fast Möbius Transforms......Page 327
  3.3 Modular Arithmetic......Page 331
 4 Fast Join Operations......Page 332
  4.1 Möbius Transforms for Dominating Set and Independent Dominating Set......Page 333
  4.2 Count and Filter: Strong Stable Set, Perfect Code and Perfect Dominating Set......Page 335
  4.3 Fourier Transforms for Induced Bounded Degree or p-Regular Subgraph......Page 337
  4.4 Möbius Transforms with a Different Partial Order for Total Dominating Set......Page 338
 5 Bringing It Together: Faster Algorithms for [,]-Domination......Page 340
 6 Conclusion......Page 345
 References......Page 346
Author Index......Page 349