Computing Reviews

Parameterized algorithms
Cygan M., Fomin F., Kowalik Ł., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S., Springer International Publishing,New York, NY,2015. 613 pp.Type:Book
Date Reviewed: 04/13/17

There are 36 definitions of complexity like the 36 flavors of ice cream! In simplest terms, complexity refers to the amount of resources consumed to execute an algorithm (resources here imply running time, space, computational effort, and so on). While classical algorithmic complexity is expressed as a function of the size of the input, parameterized complexity is its refined version, in which the complexity is expressed in terms of multiple parameters of the input, the input size being only one of them. For example, the parameters of the input probability distribution can be the other factors. The first systematic work on parameterized complexity was done by R. G. Downey and M. R. Fellows. [1] The present work serves a twofold objective. First, it introduces the reader to those problems that can be subjected to parameterized complexity analysis. Second, it teaches how to do such analysis, describing some of the latest methods in this area.

The book is organized in three parts. Part 1 gives the basic toolbox. Chapter 1 gives a formal introduction where the technical terms are defined and explained. In the subsequent six chapters, the authors proceed to explain kernelization, bounded search trees, iterative compression, randomized methods in parameterized algorithms, and so on. Part 2 is on advanced algorithmic techniques and contains five chapters on advanced kernelization techniques, algebraic techniques like sieves, convolutions and polynomials, improved dynamic programming applied to tree decomposition, matroids, and so on. Part 3, “Lower Bounds,” contains topics such as fixed parameter intractability, lower bounds based on the exponential time hypothesis, and lower bounds for kernelization.

I enjoyed reading this book, which is a good textbook for graduate and advanced undergraduate students of computer science. Each chapter contains sufficient exercises with hints whenever necessary and helpful bibliographic notes. I found the references quite comprehensive, and the index was quite useful.

The authors have, however, missed the important role that factorial experiments (as used by statisticians like me) can play in studying the interactive effects of the input parameters, when these are allowed to simultaneously vary, on the complexity of the underlying algorithm. Nevertheless, this is the best book I have seen on the topic. I strongly recommend it.


1)

Downey, R. G.; Fellows, M. R. Parameterized complexity. Springer-Verlag, New York, NY, 1999.

Reviewer:  Soubhik Chakraborty Review #: CR145193 (1706-0341)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy