Parameterized Algorithms

This comprehensive textbook presents a clean and coherent account of most fundamental tools and techniques in Parameterized Algorithms and is a self-contained guide to the area. The book covers many of the recent developments of the field, including application of important separators, branching based on linear programming, Cut & Count to obtain faster algorithms on tree decompositions, algorithms based on representative families of matroids, and use of the Strong Exponential Time Hypothesis. A number of older results are revisited and explained in a modern and didactic way.

The book provides a toolbox of algorithmic techniques. Part I is an overview of basic techniques, each chapter discussing a certain algorithmic paradigm. The material covered in this part can be used for an introductory course on fixed-parameter tractability. Part II discusses more advanced and specialized algorithmic ideas, bringing the reader to the cutting edge of current research. Part III presents complexity results and lower bounds, giving negative evidence by way of W[1]-hardness, the Exponential Time Hypothesis, and kernelization lower bounds.

All the results and concepts are introduced at a level accessible to graduate students and advanced undergraduate students. Every chapter is accompanied by exercises, many with hints, while the bibliographic notes point to original publications and related work.

這本全面的教科書提供了對參數化算法中最基本的工具和技巧的清晰且連貫的介紹，是這個領域的自成體系指南。該書涵蓋了該領域的許多最新發展，包括重要分離器的應用、基於線性規劃的分支、使用Cut & Count在樹分解上獲得更快的算法、基於代表性簇的算法、以及強指數時間假設的應用。一些較早的結果也以現代且教學性的方式重新討論和解釋。

該書提供了一個算法技巧的工具箱。第一部分是基本技巧的概述，每一章討論一個特定的算法範例。這部分的內容可以用於介紹固定參數可解性的入門課程。第二部分討論更高級和專門的算法思想，將讀者帶到當前研究的前沿。第三部分介紹了複雜性結果和下界，通過W[1]-難度、指數時間假設和核化下界提供了負面證據。

所有的結果和概念都以研究生和高年級本科生可以理解的水平介紹。每一章都附有練習題，其中許多有提示，而參考文獻則指向原始出版物和相關工作。