Invitation to Fixed-Parameter Algorithms

Theoretical computer science as the borderline between mathematics and computer science is a wonderland of fast evolving theories, challenging open problems and plentiful algorithmic and complexity results, all backed up by practical motivation and applications in computing. One of the recently opened and intensively studied directions is the so-called Fixed-Parameter Complexity, designed and developed in the 1990s by Downey and Fellows. Peppered with practical questions of solving problems with small parameter values, problems that are computationally hard in general, this is a surprisingly rich theory, where computational classes are defined based on precise logic constructions. It has immediately become popular among researchers; every major computer science conference gets a number of presentations from this area, and specialized workshops are now regularly organized. And yet, only one monograph devoted to this topic was available until recently; the book under review organically complements this previously published monograph (Downey-Fellows, Parametrized Complexity, 1999).
Downey and Fellows, the gurus of FPT (Fixed Parameter Tractability), introduce the theory by concentrating more on structural definitions and properties whilst Nidermeier comes in with numerous samples of FPT algorithms for particular problems. Moreover, a lot has happened since the Downey-Fellows monograph was published. The book under review is an excellent survey of new results, focused primarily on algorithmic issues.
The book is divided into three chapters. The first chapter provides necessary definitions accompanied by motivating examples and a broad exposition of the philosophy of Fixed Parameter Complexity. Don't skip this chapter if you are a novice in this area or if you want to enjoy learning new views on it. The second chapter provides a thorough catalogue of the methodology of fixed parameter algorithms. This is an encyclopaedia of methods such as kernelization, depth-bounded search trees and graph decompositions, all thoroughly explained with many examples. The third chapter gives examples of hardness reductions in Fixed Parameter Complexity Theory and describes the W[t] classes, with most attention paid to W[1] and W[2], which is where most of the natural problems lie.
The last section, called "Selected Case Studies", is a Madame Tussauds Museum of FPT. The difference is, you do not find any wax problems here; all of them are alive and developing at the time you read about them. The exposition here is influenced by the famous NP-completeness bible of Garey and Johnson: “Computers and Intractability - A guide to the Theory of NP-completeness” (1979), and the problems are described as carefully from the FPT perspective as Garey and Johnson did from the P-NP one. And not only because of this section is the book becoming as useful as Garey-Johnson's monograph.
This is an advanced textbook intended and well-suited both for researchers and graduate students in theoretical computer science. You will enjoy reading it whether you want to do research in the area or just want to learn about it. And while merrily intending the latter, you are most likely going to end up doing the former when you finish reading it.

Reviewer: 
jkrat
Book details
Author:  Publisher: 
Published: 
2006
ISBN: 
0-19-856607-7
Price: 
GBP 55
Categorisation