Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
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 (978-3-319212-74-6)
Date Reviewed: Apr 13 2017

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.

Reviewer:  Soubhik Chakraborty Review #: CR145193 (1706-0341)
1) Downey, R. G.; Fellows, M. R. Parameterized complexity. Springer-Verlag, New York, NY, 1999.
Bookmark and Share
  Featured Reviewer  
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Applications (G.2.3 )
 
 
Complexity Measures And Classes (F.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy