Parameterized algorithms. (English) Zbl 1334.90001

Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket

Cham: Springer (ISBN 978-3-319-21274-6/hbk; 978-3-319-21275-3/ebook). xvii, 613 p. (2015).

This book serves as an introduction to the field of parameterized algorithms and complexity accessible to graduate students and advanced undergraduate students. It contains a clean and coherent account of some of the most recent tools and techniques in the area. The book is organized into three parts. The first seven chapters give the basic toolbox of parameterized algorithms. The second part, consisting of Chapters 8–12, covers more advanced algorithmic techniques. The third part introduces the reader to the theory of lower bounds. Chapter 1 motivates parameterized algorithms and the notion of fixed parameter tractability with some simple examples. Chapter 2 gives an introduction to kernelization as first algorithmic paradigm for fixed-parameter tractability. Branching and bounded-depth search trees are topic of Chapter 3. Chapter 4 introduces the Iterative compression technique through three examples. Chapter 5 discusses techniques for parameterized algorithms that use randomization. Chapter 6 presents a collection of techniques that belong to the basic toolbox of parameterized algorithms. Chapter 7 introduces treewidth, which is a graph measure that has important applications for parameterized algorithms. Chapter 8 presents results that are based on a combinatorial bound on the number of so-called important separators. More advanced kernelization techniques are presented in Chapter 9. Two different types of algebraic techniques are discussed in Chapter 10. Chapter 11 deals with dynamic programming algorithms on graphs of bounded treewidth. Chapter 12 gives a gentle introduction to matroids. Chapter 13 presents tools that allow to give evidence that certain problems are not fixed-parameter tractable. Chapter 14 uses the (Strong) Exponential Time Hypothesis to give running time lower bounds that are more refined than the bounds in Chapter 13. Chapter 15 gives the tools for showing lower bounds for kernelization algorithms.

Reviewer: Paulo Mbunga (Kiel)

MSC:

90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
00A69	General applied mathematics
00-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematics in general
00A05	Mathematics in general
00A06	Mathematics for nonmathematicians (engineering, social sciences, etc.)
05-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
65K05	Numerical mathematical programming methods
68Q25	Analysis of algorithms and problem complexity
90C60	Abstract computational complexity for mathematical programming problems
90C39	Dynamic programming

Keywords:

kernelization; bounded search trees; iterative compression; randomized methods in parameterized algorithms; treewidth; matroids; cuts and separators; lower bounds; Exponential-Time Hypothesis; dynamic programming on treewidth