An Overview of Techniques for Designing Parameterized Algorithms <s> INTRODUCTION <s> An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now. The book is as self-contained as possible and includes a great deal of background material. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> INTRODUCTION <s> We describe some new, simple and apparently general methods for designing FPT algorithms, and illustrate how these can be used to obtain a significantly improved FPT algorithm for the MAXIMUM LEAF SPANNING TREE problem. Furthermore, we sketch how the methods can be applied to a number of other well-known problems, including the parametric dual of DOMINATING SET (also known as NONBLOCKER), MATRIX DOMINATION, EDGE DOMINATING SET, and FEEDBACK VERTEX SET FOR UNDIRECTED GRAPHS. The main payoffs of these new methods are in improved functions f(k) in the FPT running times, and in general systematic approaches that seem to apply to a wide variety of problems. <s> BIB002 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> INTRODUCTION <s> This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems. <s> BIB003 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> INTRODUCTION <s> Data reduction is a preprocessing technique which makes huge and seemingly intractable instances of a problem small and tractable. This technique is often acknowledged as one of the most powerful methods to cope with the intractability of certain NP-complete problems. Heuristics for reducing data can often be seen as reduction rules, if considered from a parameterized complexity viewpoint. Using reduction rules to transform the instances of a parameterized problem into equivalent instances, with size bounded by a function of the parameter, is known as kernelization. This thesis introduces and develops an approach to designing FPT algorithms based on effective kernelizations. This method is called the method of extremal structure. The method operates following a paradigm presented by two lemmas, the kernelization and boundary lemmas. The boundary lemma is used to find theoretical bounds on the maximum size of an instance reduced under an adequate set of reduction rules. The kernelization lemma is invoked to decide the instances which are larger than for some function depending only on the parameter . The first aim of the method of extremal structure is to provide a systematic way to discover reduction rules for fixed-parameter tractable problems. The second is to devise an analytical way to find theoretical bounds for the size of kernels for those problems. These two aims are achieved with the aid of combinatorial extremal arguments. Furthermore, this thesis shows how the method of extremal structure can be applied to effectively solve several NP-complete problems, namely MAX CUT, MAX LEAF SPANNING TREE, NONBLOCKER, -STAR PACKING, EDGE-DISJOINT TRIANGLE PACKING, MAX INTERNAL SPANNING TREE and MINIMUM MAXIMAL MATCHING. <s> BIB004 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> INTRODUCTION <s> PART I: FOUNDATIONS 1. Introduction to Fixed-Parameter Algorithms 2. Preliminaries and Agreements 3. Parameterized Complexity Theory - A Primer 4. Vertex Cover - An Illustrative Example 5. The Art of Problem Parameterization 6. Summary and Concluding Remarks PART II: ALGORITHMIC METHODS 7. Data Reduction and Problem Kernels 8. Depth-Bounded Search Trees 9. Dynamic Programming 10. Tree Decompositions of Graphs 11. Further Advanced Techniques 12. Summary and Concluding Remarks PART III: SOME THEORY, SOME CASE STUDIES 13. Parameterized Complexity Theory 14. Connections to Approximation Algorithms 15. Selected Case Studies 16. Zukunftsmusik References Index <s> BIB005
The field of parameterized algorithms continues to grow. It is a sign of its success that in the literature today there exists over 20 differently named techniques for designing parameterized algorithms. BIB001 Many parameterized algorithms build on the same ideas, and as a problem solver it is important to be familiar with these general themes and ideas. Aside from several survey articles  BIB003 , there have been at least two comprehensive texts written on parameterized algorithm design: Downey and Fellows's seminal book 'Parameterized Complexity' BIB001 and the more recent 'Invitation to Fixed-Parameter Algorithms' BIB005 by Niedermeier. The first of these books came very early in the history of parameterized complexity, and does therefore not include newer ideas. The second book is dedicated to algorithmic techniques, and singles out bounded search trees and kernelization as the two major ones, while the generic heading 'Further Algorithmic Techniques' is devoted to integer linear programming, color coding, dynamic programming and tree decompositions. In this paper, we survey what we consider to be the nine most important general techniques, namely: bounded search trees, greedy localization, color coding, local reductions, global reductions (crown reductions), iterative compression, extremal method, well-quasi-ordering (graph minors) and imposing fixed-parameter tractable (FPT) structure (treewidth). We classify these techniques under the four main themes of branching, kernelization, induction and win/win (see Fig. 1 ). In addition to its pedagogic value, we believe that such a taxonomy could help in developing both new techniques and new combinations of known techniques. The four main themes are described in separate sections. Each technique is introduced with a meta-algorithm, examples of its use are given, and we end with a brief discussion of its practicality. Regarding practicality, let us right away remark that in our opinion the most important decision is the choice of parameter. However, this issue is orthogonal to the algorithmic technique used and will thus not be discussed here. Some aspects of this classification are novel, for example, the grouping of greedy localization and color coding together with bounded search trees under the heading of Branching algorithms, and the placement of the extremal method as the maximization counterpart of iterative compression under the heading of induction. We give a generic and formal description of greedy localization that encompasses problems hitherto not known to be FPT solvable by this technique. Sometimes a technique is known under different names BIB005 or it is a variant of a more general technique. BIB002 Clearly, the fastest FPT algorithm for a problem will usually combine several techniques. In some cases such a combination has itself been given a separate name. BIB004 We do not consider all these variations of the most general techniques, and our discussion is restricted to the first two levels of the hierarchy in Fig. 1 . A note on notation: the chosen parameter for a problem is usually not stated explicitly, instead we use the convention that the variable name k always denotes the parameter. We use standard notation for graphs and focus on graph problems, particularly the following handful of quite famous ones: k-vertex cover (are there k vertices incident to all edges?), k-dominating set (are there k vertices adjacent to all vertices?), k-independent set (are there k pairwise nonadjacent vertices?), k-feedback vertex set (are there k vertices whose removal gives an acyclic graph?) and k-packing of H (are there k vertex disjoint copies of H?). All these problems are NP-hard, and our goal is an FPT algorithm, meaning that on input (G, k) for a graph G on n vertices it solves the problem in time f(k)n O BIB001 . Using the O* notation that hides not only constants but also polynomial dependencies this runtime is simply expressed as O* (f(k)).