The idea for this book was conceived over the second bottle of Villa Maria's Caber net Medot '89, at the dinner of the Australasian Combinatorics Conference held at Palmerston North, New Zealand in December 1990, where the authors first met and discovered they had a number of interests in common. Initially, we embarked on a small project to try to formulate reductions to address the apparent parame terized intractability of DOMINATING SET, and to introduce a structure in which to frame our answers. Having spent several months trying to get the definitions for the reductions right (they now seem so obvious), we turned to our tattered copies of Garey and Johnson's work [239]. We were stunned to find that virtually none of the classical reductions worked in the parameterized setting. We then wondered if we'd be able to find any interesting reductions. Several years, many more bottles, so many papers, and reductions later it [3] seemed that we had unwittingly stumbled upon what we believe is a truly central and new area of complexity theory. It seemed to us that the material would be of great interest to people working in areas where exact algorithms for a small range of parameters are natural and useful (e. g. , Molecular Biology, VLSI design). The tractability theory was rich with distinctive and powerful techniques. The intractability theory seemed to have a deep structure and techniques all of its own.
Author(s): Rodney G. Downey, Michael R. Fellows
Series: Monographs in Computer Science
Publisher: Springer
Year: 1999
Language: English
Pages: 533
Tags: Combinatorics; Algorithm Analysis and Problem Complexity
Front Matter....Pages i-xv
Computers, Complexity, and Intractability from the Parametric Point of View....Pages 1-20
Front Matter....Pages 21-21
The Basic Definitions....Pages 23-28
Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel....Pages 29-48
Optimization Problems, Approximation Schemes, and Their Relation with FPT ....Pages 49-60
The Advice View Revisited and LOGSPACE ....Pages 61-66
Methods via Automata and Bounded Treewidth....Pages 67-142
Well-Quasi-Orderings and the Robertson-Seymour Theorems....Pages 143-209
Miscellaneous Techniques....Pages 211-223
Front Matter....Pages 225-225
Reductions....Pages 227-234
The Basic Class W [1] and an Analog of Cook’s Theorem....Pages 235-254
Some Other W [1]-Hardness Results....Pages 255-281
The W -Hierarchy....Pages 283-313
Beyond W [ t ]-Hardness....Pages 315-330
Fixed Parameter Analogs of PSPACE and k -Move Games....Pages 331-340
Provable Intractability: The Class X P ....Pages 341-350
Front Matter....Pages 351-351
Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions....Pages 353-362
Relationships with Classical Complexity and Limited Nondeterminism....Pages 363-375
The Monotone and Antimonotone Collapse Theorems: MONOTONE W [2 t + 1] = W [2 t ] and ANTIMONOTONE W [2 t + 2] = W [2 t + 1]....Pages 377-387
The Structure of Languages Under Parameterized Reducibilities....Pages 389-437
Back Matter....Pages 439-533
