Invitation to fixed parameter algorithms.

*(English)*Zbl 1095.68038
Oxford Lecture Series in Mathematics and its Applications 31. Oxford: Oxford University Press (ISBN 0-19-856607-7/hbk). xi, 300 p. (2006).

This book is devoted to fixed-parameter algorithms, the concept that is fundamental for the algorithmics of computationally hard discrete problems. This problem is very general. It covers important topics of classical algorithmic methods – in particular, parameterized complexity theory, depth-bounded search trees, tree decompositions of graphs, and the essentials of hardness theory.

The book has three parts. The first part, “Foundations”, introduces to fixed-parameterized complexity theory. The second part of this book, “Algorithmic methods”, studies methods that provide the basic methodology in some problems, such as kernelization, automated search tree generation, dynamic programming (knapsack problem, Steiner problem in graphs, multicommodity demand flow in trees), tree decompositions in graphs, etc. The third part of this book, “Some theory, some case studies”, provides the essentials of parameterized hardness theory, focusing first on W[1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Bibliographical, and general comments, reflecting the author’s point of view on the future development of fixed-parameter algorithms and related parameterized hardness theory, are given at the end of the book.

The first two parts of the book are written at a level for use in a graduate course on algorithmics of computationally hard discrete problems. It should also appeal to professional programmers, algorithm designers, and computer scientists wishing to learn about complexity theory or to use new methods for solving real-life problems. The third part is written at a higher level. It can be used by research mathematicians and in a special course on parameterized complexity theory for Ph.D. students in computer science and mathematics.

The book has three parts. The first part, “Foundations”, introduces to fixed-parameterized complexity theory. The second part of this book, “Algorithmic methods”, studies methods that provide the basic methodology in some problems, such as kernelization, automated search tree generation, dynamic programming (knapsack problem, Steiner problem in graphs, multicommodity demand flow in trees), tree decompositions in graphs, etc. The third part of this book, “Some theory, some case studies”, provides the essentials of parameterized hardness theory, focusing first on W[1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Bibliographical, and general comments, reflecting the author’s point of view on the future development of fixed-parameter algorithms and related parameterized hardness theory, are given at the end of the book.

The first two parts of the book are written at a level for use in a graduate course on algorithmics of computationally hard discrete problems. It should also appeal to professional programmers, algorithm designers, and computer scientists wishing to learn about complexity theory or to use new methods for solving real-life problems. The third part is written at a higher level. It can be used by research mathematicians and in a special course on parameterized complexity theory for Ph.D. students in computer science and mathematics.

Reviewer: Jerzy Martyna (Kraków)

##### MSC:

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

68R10 | Graph theory (including graph drawing) in computer science |

68W40 | Analysis of algorithms |

90C39 | Dynamic programming |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |