Parameterized Complexity

This monograph presents an approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. This will be suitable for graduate students and researchers in computer science and mathematics, particularly those studying complexity theory.

1 Computers, Complexity, and Intractability from the Parametric Point of View.- 1.1 Introduction.- 1.2 The Role of Computational Complexity in Modern Science.- 1.3 The Story of Dr.O, Continued.- 1.4 Reworking the Foundations of Computational Complexity.- 1.5 A Deal with the Devil.- 1.6 How Parameters Arise in Practice.- 1.7 A Distinctive Positive Toolkit.- 1.8 O No?.- 1.9 The Barometer of Parametric Intractability.- 1.10 Structural Aspects of Parameterized Complexity.- 1.11 An Overview of Current Research Horizons.- I Parameterized Tractability.- 2 The Basic Definitions.- 2.1 Fixed-Parameter Tractability.- 2.2 The Advice View.- 3 Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel.- 3.1 The Method of Bounded Search Trees.- 3.1.1 The Basic Method.- 3.1.2 Heuristic Improvements, Shrinking the Search Tree.- 3.2 The Method of Reduction to a Problem Kernel.- 3.2.1 The Basic Method.- 3.2.2 Hereditary Properties and Leizhen Cai’s Theorem.- 4 Optimization Problems, Approximation Schemes, and Their Relation with FPT.- 4.1 Optimization Problems.- 4.2 How FPT and Optimization Problems Relate.- 4.3 The Classes MAXSNP, MIN F+?1(h), and FPT.- 5 The Advice View Revisited and LOGSPACE.- 6 Methods via Automata and Bounded Treewidth.- 6.1 Classical Automata Theory.- 6.1.1 Deterministic Finite Automata.- 6.1.2 Nondeterministic Finite Automata.- 6.1.3 Regular Languages.- 6.1.4 The Myhill―Nerode Theorem and the Method of Test Sets.- 6.1.5 Classical Tree Automata.- 6.2 Treewidth.- 6.3 Bodlaender’s Theorem.- 6.4 Parse Trees for Graphs of Bounded Treewidth and an Analog of the Myhill―Nerode Theorem.- 6.5 Courcelle’s Theorem.- 6.5.1 The Basic Theorem.- 6.5.2 Implementing Courcelle’s Theorem.- 6.6 Seese’s Theorem.- 6.7 Notes on MS1 Theory.- 7 Well-Quasi-Orderings and the Robertson-Seymour Theorems.- 7.1 Basic WQO Theory.- 7.2 Thomas’ Lemma.- 7.2.1 Thomas’ Lemma Fails for Path Decompositions.- 7.3 The Graph Minor Theorem for Bounded Treewidth.- 7.4 Excluding a Forest.- 7.5 Connections with Automata Theory and Boundaried Graphs.- 7.6 A Sketch of the Proof of the Graph Minor Theorem.- 7.7 Immersions and the Nash-Williams Conjecture.- 7.8 Applications of the Obstruction Principle and WQO’s.- 7.9 Effectivizations of Obstruction-Based Methods.- 7.9.1 Effectivization by Self-Reduction.- 7.9.2 Effectivization by Obstruction Set Computation.- 8 Miscellaneous Techniques.- 8.1 Depth-First Search.- 8.2 Bounded-Width Subgraphs, the Plehn-Voigt Theorem, and Induced Subgraphs.- 8.3 Hashing.- II Parameterized Intractability.- 9 Reductions.- 10 The Basic Class W[1] and an Analog of Cook’s Theorem.- 11 Some Other W[1]-Hardness Results.- 12 The W -Hierarchy.- 13 Beyond W[t]-Hardness.- 14 Fixed Parameter Analogs of PSPACE and k-Move Games.- 15 Provable Intractability: The Class XP.- III Structural and Other Results.- 16 Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions.- 17 Relationships with Classical Complexity and Limited Nondeterminism.- 17.1 Classical Complexity.- 17.2 Nondeterminism in P, LOGNP, and the Cai-Chen Model and Other Models.- 18 The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONEW[2t + 2] = W[2t + 1].- 19 The Structure of Languages Under Parameterized Reducibilities.- 19.1 Some Tools.- 19.2 Results.- IV Appendix.- A A Problem Compendium and Guide to W-Hierarchy Completeness, Hardness, and Classification; and Some Research Horizons.- B Research Horizons.- B.2 A Lineup of Tough Customers.- B.3 Connections Between Classical and Parameterized Complexity.- B.4 Classification Gaps.- B.5 Structural Issues and Analogs of Classical Results.- References.