Fundamentals of parameterized complexity
type: Item
instance of: scholarly article
title: Fundamentals of parameterized complexity
zbMATH Open document ID: 1358.68006
DOI: 10.1007/978-1-4471-5559-1
author: Rodney G. Downey
author: Michael R. Fellows
published in: Texts in Computer Science
publication date: 2013-12-06T00:00:00Z
review text: The standard way to investigate the efficiency of an algorithm \(A\) that solves a computational problem \(P\) is to do a worst-case analysis: One considers the input length as a parameter, typically denoted by \(n\), and stipulates that the time spent by \(A\) to solve \(P\) is a function of \(n\), defined as the maximum running time of \(A\) taken over all inputs of length \(n\). This one-dimensional approach is often too rough and the defining idea of parameterized complexity is to slice the input space in a finer way, considering other parameters as well, besides the input length. Many people consider that the authors of this book, Rodney Downey and Michael Fellows, have started the field with a series of papers in the 90s and especially with their book [Parameterized complexity. Berlin: Springer (1998; Zbl 0914.68076)]. This field is now solid and dynamic, with meaningful and deep results. It should be said from the beginning that the present book is not a revised version of the 1998 book. It is a new book that conveys a detailed picture of parameterized complexity as it stands today. The book is structured in nine parts. Part 1 (Chapters 1--2) presents some preliminaries from classical complexity theory and the basic definitions. Part 2 (Chapters 3--9) covers the most important techniques in parameterized algorithmics. These techniques include: bounded search trees, kernelization, iterative compression, measure-and-conquer, greedy localization, color coding, randomized divide-and-conquer, and others. Part 3 (Chapters 10--16) is dedicated to another family of techniques used in the design of parameterized algorithms that are based on structural properties of graphs (primarily), but also of other objects, such as matroids or polynomials. The generic approach is to use so-called width metrics which quantify how close is the input to having a certain graph property, such as being a tree, or a complete graph, and so on. The book presents treewidth, branchwidth, cli…
reviewed by: Marius Zimand
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W01
zbMATH DE Number: 6236169
zbMATH Keywords: computational complexity
zbMATH Keywords: algorithms
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-1-4471-5559-1
OpenAlex ID: W2116087731
Recommended article: Parameterized complexity: the main ideas and connections to practical computing
Recommended article: Q4417671
Recommended article: A Basic Parameterized Complexity Primer
Recommended article: Q4393480
Recommended article: Q4474097
Recommended article: A Parameterized Complexity Tutorial
Recommended article: Computation Models for Parameterized Complexity
Recommended article: Polynomial time approximation schemes and parameterized complexity
Recommended article: Mathematical Foundations of Computer Science 2004
description: scientific article; zbMATH DE number 6236169