This textbook deals with exact algorithms for NP-complete graph problems. Three methods are illustrated by examples: fixed-parameter algorithms, exponential time algorithms that are faster than their naïve counterparts, and restrictions to classes of graphs that can be decomposed in a tree-like fashion. A first part recalls all the foundations used later on: graphs, logic and complexity theory. The short chapter on fpt-algorithms starts with the classical example, vertex cover and its generalisation, hitting set, and continues with graph modification problems. There is more on fast exponential time algorithms: a chapter on vertex colouring that analyses {\it E. L. Lawler}’s algorithm [“A note on the complexity of the chromatic number problem,” Inf. Process. Lett. 5, 66‒67 (1976; Zbl 0336.68021)] and presents the CSP-approach by {\it R. Beigel} and {\it D. Eppstein} [“3-coloring in time $O(1.3289^n)$,” J.~Algorithms 54, 168‒204 (2005; Zbl 1101.68716)], and another chapter that deals with the dynamic programming algorithm by {\it M. Held} and {\it R. M. Karp} [“A dynamic programming approach to sequencing problems,” J. Soc. Ind. Appl. Math. 10, 196‒210 (1962; Zbl 0106.14103)] for TSP, and the “measure and conquer” approach by {\it F. V. Fomin}, {\it F. Grandoni}, and {\it D. Kratsch} [New York, NY: ACM Press. (2005; Zbl 1073.68886) and “Measure and conquer: Domination ‒ a case study,” Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11‒15, 2005. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 3580, 191‒203 (2005; Zbl 1082.68866)] for the domatic number problem. The method of decomposition trees is illustrated by algorithms for co-graphs by {\it D. G. Corneil}, {\it H. Lerchs}, and {\it L. Stewart Burlingham} [“Complement reducible graphs,” Discrete Appl. Math. 3, 163‒174 (1981; Zbl 0463.05057)] and for graphs of bounded tree- or clique-width. Besides the dynamic programming algorithms working directly on the deomposition tree, the authors explain connections between different width parameters and the link to monadic second order logic. This textbook aims at students of Computer Science and does not compete with research monographs in the field such as those by {\it R. G. Downey} and {\it M. R. Fellows} [Parameterized complexity. Texts and Monographs in Computer Science. Berlin: Springer(1998; Zbl 0914.68076)], {\it J. Flum} and {\it M. Grohe} [Parametrized complexity theory, Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer (2006; Zbl 1143.68016)], {\it R. Niedermeier} [Invitation to fixed parameter algorithms. Oxford Lecture Series in Mathematics and its Applications 31. Oxford: Oxford University Press. (2006; Zbl 1095.68038)], {\it F. V. Fomin} and {\it D. Kratsch} [Exact exponential algorithms. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer. (2011; Zbl 05817382)], and {\it A. Brandstädt}, {\it Van Bang Le}, and {\it J. P. Spinrad} [Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, 3. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. (1999; Zbl 0919.05001)], even if there is some overlap. Because of its self-contained construction, illustrations, exercises and references to original sources the book can guide private studies. More likely, a course on recent developments in graph algorithms will be based on it.
Reviewer: Haiko Müller (Leeds)