Parametrized complexity theory. (Q2488567): Difference between revisions

In many algorithmical problems, the input has several distinct components whose lengths can be vastly different. We can break the input into two parts, one having length \(k\) and the other having length \(n\), with the expectation that \(k\ll n\) (for example \(n\) is the length of a database and \(k\) is the length of a query to the database). Such problems are called parametrized problems and \(k\) is called the parameter. Problems solvable by algorithms running in time \(f(k) \cdot \text{ poly}(n)\), may be in practice quite feasible even if \(f\) is a fast-growing function. The class of such problems is called FPT (Fixed-Parameter Tractable Problems). Some parameterized problems do not seem to be in FPT and it is important to develop tools that help us understand why this is so. This is the goal of parameterized complexity theory, the object of the monograph/textbook by Jörg Flum and Martin Grohe, two researchers with important contributions in this active and important field. The book is structured in three parts. Part 1 (Chapters 2--8) gives a comprehensive coverage of the main concepts in this theory: fpt reductions, the main complexity classes (the W-hierarchy and the A-hierarchy), the known relations between these classes, complete problems for the first and second levels of these hierarchies, machine characterizations of the classes. The levels of the W-hierarchy (and of the A-hierarchy) are defined in a uniform way as the closure under fpt reductions of a problem involving finite structures and first-order logic formulas; the difference between classes comes solely from the number of quantifier alternations in the formula. Part 2 (Chapters 9--13) presents techniques that are used in the design of fpt-algorithms. Chapter 9 describes kernelization, which consists in reducing an instance of a parametrized problem to another instance of the same problem such that the size of the latter is bounded in terms of the parameter \(k\). Chapter 10 presents the automata-theoretic method which is appropriate for logic-based problems such as model-checking or database query evaluations. This chapter also includes super-exponential lower bounds for model checking of monadic second-order formulas on trees. Chapters 11 and 12 present fpt algorithms for graph problems in the case of graphs that have bounded tree width, or that have bounded local tree width, or that are planar. Chapter 13 is about homomorphism and embedding problems for special classes of finite structures. Part 3 (Chapters 14--16) returns to complexity and addresses more refined issues that go beyond the basic concepts from Part 1. Chapter 14 is about the parameterized complexity of counting problems. Chapters 15 and 16 investigate the cases when the function \(f\) (from the definition of an fpt-algorithm) is required to be at most exponential or sub-exponential. The book is comprehensive and up-to-date. Nevertheless, the authors planned it as a textbook and they have succeeded in their goal. The definitions are illustrated by good examples, the proofs are complete and proceed at a convenient pace, the connections and the implications of the results are spelled out clearly, the exercises are relevant. The book is recommended to specialists as a work of reference, as well as to beginners who want a solid introduction to the theory of parametrized computational problems.