Parameterized complexity

Chapter 1 Computers, Complexity, and Intractability from the Parametric Point of View

Chapter 2 The Basic Definitions

Chapter 3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel

Chapter 4 Optimization Problems, Approximation Schemes, and Their Relation with FPT

Chapter 5 The Advice View Revisited and LOGSPACE

Chapter 6 Methods via Automata and Bounded Treewidth

Chapter 7 Well-Quasi-Orderings and the Robertson-Seymour Theorems

Chapter 8 Miscellaneous Techniques

Chapter 9 Reductions

Chapter 10 The Basic Class W [1] and an Analog of Cook’s Theorem

Chapter 11 Some Other W [1]-Hardness Results

Chapter 13 Beyond W [ t ]-Hardness

Chapter 14 Fixed Parameter Analogs of PSPACE and k -Move Games

Chapter 15 Provable Intractability: The Class X P

Chapter 16 Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions

Chapter 17 Relationships with Classical Complexity and Limited Nondeterminism

Chapter 18 The Monotone and Antimonotone Collapse Theorems: MONOTONE W [2 t + 1] = W [2 t ] and ANTIMONOTONE W [2 t + 2] = W [2 t + 1]

Chapter 19 The Structure of Languages Under Parameterized Reducibilities