Parameterized Complexity Book

	Preface
	Acknowledgements
	List of Figures
1	Computers, Complexity, and Intractability from the Parametric Point of View	1
I	Parameterized Tractability	21
2	The Basic Definitions	23
3	Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel	29
4	Optimization Problems, Approximation Schemes, and Their Relation with FPT	49
5	The Advice View Revisited and LOGSPACE	61
6	Methods via Automata and Bounded Treewidth	67
7	Well-Quasi-Orderings and the Robertson-Seymour Theorems	143
8	Miscellaneous Techniques	211
II	Parameterized Intractability	225
9	Reductions	227
10	The Basic Class W[1] and an Analog of Cook's Theorem	235
11	Some Other W[1]-Hardness Results	255
12	The W-Hierarchy	283
13	Beyond W[t]-Hardness	315
14	Fixed Parameter Analogs of PSPACE and k-Move Games	331
15	Provable Intractability: The Class XP	341
III	Structural and Other Results	351
16	Another Basis for the W-Hierarchy, the Tradeoff-Theorem, and Randomized Reductions	353
17	Relationships with Classical Complexity and Limited Nondeterminism	363
18	The Monotone and Antimonotone Collapse Theorems: Monotone W[2t + 1] = W[2t] and Antimonotone W[2t + 2] = W[2t + 1]	377
19	The Structure of Languages Under Parameterized Reducibilities	389
A	A Problem Compendium and Guide to W-Hierarchy Completeness, Hardness, and Classification; and Some Research Horizons	441
B	Research Horizons	481
	References	489
	Index	517