zbMATH — the first resource for mathematics

Kernelization. Theory of parameterized preprocessing. (English) Zbl 1426.68003
Cambridge: Cambridge University Press (ISBN 978-1-107-05776-0/hbk; 978-1-107-41515-7/ebook). xiv, 515 p. (2019).
This book studies the research area of kernelization, which consists of the techniques used for data reduction via pre-processing in order to speed up data analysis computations. It covers a large number of areas and consists of 24 chapters grouped into four parts. The book begins with an introduction to kernelization, presenting the key definitions and background theorems for pre-processing derived from graph theory. The second part of the book considers reductions that are based on trees or tree-like structures of graphs, including dynamic programming methods. The last two parts of the book consider more advanced but efficient techniques of kernelization, which are derived from more complex graph theory ideas, such as distillation, Ramsey theory and Steiner trees, as well as lossy approaches to kernelization. Although the book explores very novel and complex ideas, it is well written with attention to detail and easy to follow. The book concludes with a useful list of relevant references.

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68P01 General topics in the theory of data
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
68W01 General topics in the theory of algorithms
90C27 Combinatorial optimization
Full Text: DOI