Fundamentals of Parameterized Complexity

<p>Introduction</p><p>Part I: Parameterized Tractability</p><p>Preliminaries</p><p>The Basic Definitions</p><p>Part II: Elementary Positive Techniques</p><p>Bounded Search Trees</p><p>Kernelization</p><p>More on Kernelization</p><p>Iterative Compression, and Measure and Conquer, for Minimization Problems</p><p>Further Elementary Techniques</p><p>Colour Coding, Multilinear Detection, and Randomized Divide and Conquer</p><p>Optimization Problems, Approximation Schemes, and Their Relation to FPT</p><p>Part III: Techniques Based on Graph Structure</p><p>Treewidth and Dynamic Programming</p><p>Heuristics for Treewidth</p><p>Automata and Bounded Treewidth</p><p>Courcelle's Theorem</p><p>More on Width-Metrics: Applications and Local Treewidth</p><p>Depth-First Search and the Plehn-Voigt Theorem</p><p>Other Width Metrics</p><p>Part IV: Exotic Meta-Techniques</p><p>Well-Quasi-Orderings and the Robertson-Seymour Theorems</p><p>The Graph Minor Theorem</p><p>Applications of the Obstruction Principle and WQOs</p><p>Part V: Hardness Theory</p><p>Reductions</p><p>The Basic Class W[1] and an Analog of Cook's Theorem</p><p>Other Hardness Results</p><p>The W-Hierarchy</p><p>The Monotone and Antimonotone Collapses</p><p>Beyond W-Hardness</p><p>k-Move Games</p><p>Provable Intractability: The Class XP</p><p>Another Basis</p><p>Part VI: Approximations, Connections, Lower Bounds</p><p>The M-Hierarchy, and XP-optimality</p><p>Kernelization Lower Bounds</p><p>Part VII: Further Topics</p><p>Parameterized Approximation</p><p>Parameterized Counting and Randomization</p><p>Part VIII: Research Horizons</p><p>Research Horizons</p><p>Part IX Appendices</p><p>Appendix 1: Network Flows and Matchings</p><p>Appendix 2: Menger's Theorems</p>