An Overview of Techniques for Designing Parameterized Algorithms
---
paper_title: Parameterized Complexity

paper_content:

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.
---
paper_title: Invitation to fixed-parameter algorithms

paper_content:

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
---
paper_title: SYSTEMATIC KERNELIZATION IN FPT ALGORITHM DESIGN

paper_content:

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.
---
paper_title: Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT

paper_content:

This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.
---
paper_title: Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems

paper_content:

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.
---
paper_title: On the Differences between ``Practical'' and ``Applied''

paper_content:

The terms “practical” and “applied” are often used synonymously in our community. For the purpose of this talk I will assign more precise, distinct meanings to both terms (which are not intended to be ultimate definitions). More specifically, I will reserve the word “applied” for work whose crucial, central goal is finding a feasible, reasonable (e.g. economical) solution to a concrete real-world problem, which is requested by someone outside theoretical computer science for his or her own work.
---
paper_title: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems

paper_content:

We obtain faster algorithms for problems such as r-dimensional matching, r-set packing, graph packing, and graph edge packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). Previously such a kernel was known only for triangle packing. This technique lets us combine, in a new and sophisticated way, Alon, Yuster and Zwick’s color-coding technique with dynamic programming on the structure of the kernel to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.
---
paper_title: Vertex Cover: Further Observations and Further Improvements

paper_content:

Recently, there have been increasing interests and progresses in lowering the worst case time complexity for well-known NP-hard problems, in particular for the VERTEX COVER problem. In this paper, new properties for the VERTEX COVER problem are indicated and several new techniques are introduced, which lead to a simpler and improved algorithm of time complexity O(kn + 1:271kk2) for the problem. Our algorithm also induces improvement on previous algorithms for the INDEPENDENT SET problem on graphs of small degree.
---
paper_title: An FPT Algorithm for Set Splitting

paper_content:

An FPT algorithm with a running time of O(n 4 + 2 O(k) n 2.5 ) is described for the SET SPLITTING problem, parameterized by the number k of sets to be split. It is also shown that there can be no FPT algorithm for this problem with a running time of the form 2 o(k) n c unless the satisfiability of n-variable 3SAT instances can be decided in time 2 o(n) .
---
paper_title: Reducing to independent set structure: the case of k-internal spanning tree

paper_content:

The k-INTERNAL SPANNING TREE problem asks whether a certain graph G has a spanning tree with at least k internal vertices. Basing our work on the results presented in [Prieto and Sloper 2003], we show that there exists a set of reduction rules that modify an arbitrary spanning tree of a graph into a spanning tree with no induced edges between the leaves. Thus, the rules either produce a tree with many internal vertices, effectively deciding the problem, or they identify a large independent set, the leaves, in the graph. Having a large independent set is beneficial, because then the graph allows both 'crown decompositions' and path decompositions. We show how this crown decomposition can be used to obtain a O(k2) kernel for the k-INTERNAL SPANNING TREE problem, improving on the O(k3) kernel presented in [Prieto and Sloper 2003].
---
paper_title: SYSTEMATIC KERNELIZATION IN FPT ALGORITHM DESIGN

paper_content:

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.
---
paper_title: Packing Edge Disjoint Triangles: A Parameterized View

paper_content:

The problem of packing k edge-disjoint triangles in a graph has been thoroughly studied both in the classical complexity and the approximation fields and it has a wide range of applications in many areas, especially computational biology [BP96]. In this paper we present an analysis of the problem from a parameterized complexity viewpoint. We describe a fixed-parameter tractable algorithm for the problem by means of kernelization and crown rule reductions, two of the newest techniques for fixed-parameter algorithm design. We achieve a kernel size bounded by 4k, where k is the number of triangles in the packing.
---
paper_title: Looking at the Stars

paper_content:

The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a particular family of instances of this problem, namely the packing of stars. We give a quadratic kernel for packing k copies of H = K1,s. When we consider the special case of s = 2, i.e. H being a star with two leaves, we give a linear kernel and an algorithm running in time O(25.301kk2.5 + n3).
---
paper_title: The Method of Extremal Structure on the k-Maximum Cut Problem

paper_content:

Using the Method of Extremal Structure, which combines the use of reduction rules as a preprocessing technique and combinatorial extremal arguments, we will prove the fixed-parameter tractability and find a problem kernel for k-MAXIMUM CUT. This kernel has 2k edges, the same as that found by Mahajan and Raman in (Mahajan & Raman 1999), but using our methodology we also find a bound of k vertices leading to a running time of O(k 2k/2 + n2).
---
paper_title: Bidimensionality: new connections between FPT algorithms and PTASs

paper_content:

We demonstrate a new connection between fixed-parameter tractability and approximation algorithms for combinatorial optimization problems on planar graphs and their generalizations. Specifically, we extend the theory of so-called "bidimensional" problems to show that essentially all such problems have both subexponential fixed-parameter algorithms and PTASs. Bidimensional problems include e.g. feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal problems, dominating set, edge dominating set, r-dominating set, diameter, connected dominating set, connected edge dominating set, and connected r-dominating set. We obtain PTASs for all of these problems in planar graphs and certain generalizations; of particular interest are our results for the two well-known problems of connected dominating set and general feedback vertex set for planar graphs and their generalizations, for which PTASs were not known to exist. Our techniques generalize and in some sense unify the two main previous approaches for designing PTASs in planar graphs, namely, the Lipton-Tarjan separator approach [FOCS'77] and the Baker layerwise decomposition approach [FOCS'83]. In particular, we replace the notion of separators with a more powerful tool from the bidimensionality theory, enabling the first approach to apply to a much broader class of minimization problems than previously possible; and through the use of a structural backbone and thickening of layers we demonstrate how the second approach can be applied to problems with a "nonlocal" structure.
---
paper_title: An efficient parameterized algorithm for m-set packing

paper_content:

We present an efficient parameterized algorithm solving the Set Packing problem, in which we assume that the size of the sets is bounded by m. In particular, if the size m of the sets is bounded by a constant, then our algorithm is fixed-parameter tractable. For example, if the size of the sets is bounded by 3, then our algorithm runs in time O((5.7k)kn).
---
paper_title: Using Nondeterminism to Design Efficient Deterministic Algorithms

paper_content:

In this paper, we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives an O((5.7k) k n) parameterized algorithm for the 3-D matching problem, which significantly improves the previous algorithm by Downey, Fellows, and Koblitz. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.
---
paper_title: The Spatial Complexity of Oblivious K-Probe Hash Functions

paper_content:

The problem of constructing a dense static hash-based lookup table T for a set of n elements belonging to a universe $U = \{ 0, 1, 2,\cdots , m -1 \}$ is considered. Nearly tight bounds on the spatial complexity of oblivious $O(1)$-probe hash functions, which are defined to depend solely on their search key argument, are provided. This establishes a significant gap between oblivious and nonoblivious search. In particular, the results include the following: • A lower bound showing that oblivious k-probe hash functions require a program size of $\Omega(({n / k}^{2})e^{-k}+\log \log m)$ bits, on average. • A probabilistic construction of a family of oblivious k-probe hash functions that can be specified in $O(n e^{-k} +\log \log m)$ bits, which nearly matches the above lower bound. • A variation of an explicit $O(1)$ time 1-probe (perfect) hash function family that can be specified in $O(n+\log \log m)$ bits, which is tight to within a constant factor of the lower bound.
---
paper_title: Parameterized Complexity

paper_content:

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.
---
paper_title: Linear kernels in linear time, or how to save k colors in O(n2) steps

paper_content:

This paper examines a parameterized problem that we refer to as n - k GRAPH COLORING, i.e., the problem of determining whether a graph G with n vertices can be colored using n - k colors. As the main result of this paper, we show that there exists a O(kn 2 + k 2 + 2 3.8161k ) = O(n 2 ) algorithm for n - k GRAPH COLORING for each fixed k. The core technique behind this new parameterized algorithm is kernalization via maximum (and certain maximal) matchings. The core technical content of this paper is a near linear-time kernelization algorithm for n-k CLIQUE COVERING. The near linear-time kernelization algorithm that we present for n - k CLIQUE COVERING produces a linear size (3k - 3) kernel in O(k(n + m)) steps on graphs with n vertices and m edges. The algorithm takes an instance (G, k) of CLIQUE COVERING that asks whether a graph G can be covered using |V| - k cliques and reduces it to the problem of determining whether a graph G' = (V',E') of size < 3k - 3 can be covered using |V'|-k' cliques. We also present a similar near linear-time algorithm that produces a 3k kernel for VERTEX COVER. This second kernelization algorithm is the crown reduction rule.
---
paper_title: Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets

paper_content:

We study the problem of (efficiently) deleting such clauses from conjunctive normal forms (clause-sets) which cannot contribute to any proof of unsatisfiability. For that purpose we introduce the notion of an autarky system A, which detects deletion of superfluous clauses from a clause-set F and yields a canonical normal form NA(F) ⊆ F. Clause-sets where no clauses can be deleted are called A-lean, a natural weakening of minimally unsatisfiable clause-sets opening the possibility for combinatorial approaches and including also satisfiable instances. Three special examples for autarky systems are considered: general autarkies, linear autarkies (based on linear programming) and matching autarkies (based on matching theory). We give new characterizations of ("absolutely") lean clause-sets in terms of qualitative matrix analysis, while matching lean clause-sets are characterized in terms of deficiency (the difference between the number of clauses and the number of variables), by having a cyclic associated transversal matroid, and also in terms of fully indecomposable matrices. Finally we discuss how to obtain polynomial time satisfiability decision for clause-sets with bounded deficiency, and we make a few steps towards a general theory of autarky systems.
---
paper_title: Investigations on Autark Assignments

paper_content:

Abstract The structure of the monoid of autarkies and the monoid of autark subsets for clause-sets F is investigated, where autarkies are partial (truth) assignments satisfying some subset F′⊆F (called an autark subset), while not interacting with the clauses in F⧹F′. Generalising minimally unsatisfiable clause-sets, the notion of lean clause-sets is introduced, which do not have non-trivial autarkies, and it is shown that a clause-set is lean iff every clause can be used by some resolution refutation. The largest lean sub-clause-set and the largest autark subset yield a (2-)partition for every clause-set. As a special case of autarkies we introduce the notion of linear autarkies, which can be found in polynomial time by means of linear programming. Clause-sets without non-trivial linear autarkies we call linearly lean, and clause-sets satisfiable by a linear autarky we call linearly satisfiable. As before, the largest linearly lean sub-clause-set and the largest linearly autark subset yield a (2-)partition for every clause-set, but this time the decomposition is computable in polynomial time. The class of linearly satisfiable clause-sets generalises the notion of matched clause-sets introduced in a recent paper by J. Franco and A. Van Gelder, and, as shown by H. van Maaren, contains also (“modulo Unit-clause elimination”) all satisfiable q-Horn clause-sets, introduced by E. Boros, Y. Crama and P. Hammer. The class of linearly lean clause-sets is stable under “crossing out variables” and union, and has some interesting combinatorial properties with respect to the deficiency δ=c−n, the difference of the number of clauses and the number of variables: So for example (non-empty) linearly lean clause-sets fulfill δ⩾1, where this property has been known before only for minimally unsatisfiable clause-sets.
---
paper_title: Reducing to independent set structure: the case of k-internal spanning tree

paper_content:

The k-INTERNAL SPANNING TREE problem asks whether a certain graph G has a spanning tree with at least k internal vertices. Basing our work on the results presented in [Prieto and Sloper 2003], we show that there exists a set of reduction rules that modify an arbitrary spanning tree of a graph into a spanning tree with no induced edges between the leaves. Thus, the rules either produce a tree with many internal vertices, effectively deciding the problem, or they identify a large independent set, the leaves, in the graph. Having a large independent set is beneficial, because then the graph allows both 'crown decompositions' and path decompositions. We show how this crown decomposition can be used to obtain a O(k2) kernel for the k-INTERNAL SPANNING TREE problem, improving on the O(k3) kernel presented in [Prieto and Sloper 2003].
---
paper_title: Introduction to Algorithms: A Creative Approach

paper_content:

Introduction. Mathematical Induction. Analysis of Algorithms. Data Structures. Design of Algorithms by Induction. Algorithms Involving Sequences and Sets. Graph Algorithms. Geometric Algorithms. Algebraic and Numeric Algorithms. Reductions. NP-Completeness. Parallel Algorithms.
---
paper_title: Vertex packings: Structural properties and algorithms

paper_content:

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient “local” optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a “good” algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported.
---
paper_title: Finding odd cycle transversals

paper_content:

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.
---
paper_title: Linear kernels in linear time, or how to save k colors in O(n2) steps

paper_content:

This paper examines a parameterized problem that we refer to as n - k GRAPH COLORING, i.e., the problem of determining whether a graph G with n vertices can be colored using n - k colors. As the main result of this paper, we show that there exists a O(kn 2 + k 2 + 2 3.8161k ) = O(n 2 ) algorithm for n - k GRAPH COLORING for each fixed k. The core technique behind this new parameterized algorithm is kernalization via maximum (and certain maximal) matchings. The core technical content of this paper is a near linear-time kernelization algorithm for n-k CLIQUE COVERING. The near linear-time kernelization algorithm that we present for n - k CLIQUE COVERING produces a linear size (3k - 3) kernel in O(k(n + m)) steps on graphs with n vertices and m edges. The algorithm takes an instance (G, k) of CLIQUE COVERING that asks whether a graph G can be covered using |V| - k cliques and reduces it to the problem of determining whether a graph G' = (V',E') of size < 3k - 3 can be covered using |V'|-k' cliques. We also present a similar near linear-time algorithm that produces a 3k kernel for VERTEX COVER. This second kernelization algorithm is the crown reduction rule.
---
paper_title: SYSTEMATIC KERNELIZATION IN FPT ALGORITHM DESIGN

paper_content:

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.
---
paper_title: Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems

paper_content:

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.
---
paper_title: Call routing and the ratcatcher

paper_content:

Suppose we expect there to bep(ab) phone calls between locationsa andb, all choices ofa, b from some setL of locations. We wish to design a network to optimally handle these calls. More precisely, a “routing tree” is a treeT with set of leavesL, in which every other vertex has valency 3. It has “congestion” 0 form the edges of a planar graphG, there is an efficient, strongly polynomial algorithm.
---
paper_title: Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

paper_content:

We present an algorithm that constructively produces a solution to the k-DOMINATING SET problem for planar graphs in time O(c k n), where c = 4 634 . To obtain this result, we show that the treewidth of a planar graph with domination number y(G) is O(γ(G)), and that such a tree decomposition can be found in O(γ(G)n) time. The same technique can be used to show that the k-FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c k 1n ) time, where c 1 = 3 3634 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k-DOMINATING SET, e.g., k-INDEPENDENT DOMINATING SET and k-WEIGHTED DOMINATING SET.
---
paper_title: Bidimensionality: new connections between FPT algorithms and PTASs

paper_content:

We demonstrate a new connection between fixed-parameter tractability and approximation algorithms for combinatorial optimization problems on planar graphs and their generalizations. Specifically, we extend the theory of so-called "bidimensional" problems to show that essentially all such problems have both subexponential fixed-parameter algorithms and PTASs. Bidimensional problems include e.g. feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal problems, dominating set, edge dominating set, r-dominating set, diameter, connected dominating set, connected edge dominating set, and connected r-dominating set. We obtain PTASs for all of these problems in planar graphs and certain generalizations; of particular interest are our results for the two well-known problems of connected dominating set and general feedback vertex set for planar graphs and their generalizations, for which PTASs were not known to exist. Our techniques generalize and in some sense unify the two main previous approaches for designing PTASs in planar graphs, namely, the Lipton-Tarjan separator approach [FOCS'77] and the Baker layerwise decomposition approach [FOCS'83]. In particular, we replace the notion of separators with a more powerful tool from the bidimensionality theory, enabling the first approach to apply to a much broader class of minimization problems than previously possible; and through the use of a structural backbone and thickening of layers we demonstrate how the second approach can be applied to problems with a "nonlocal" structure.
---

Title: An Overview of Techniques for Designing Parameterized Algorithms

Section 1: INTRODUCTION
Description 1: Provide a general introduction to the field of parameterized algorithms, mention the growth of the field, significant literature, and summarize the main techniques covered in the paper.

Section 2: BRANCHING ALGORITHMS
Description 2: Describe algorithms using a branching strategy, criteria for FPT running time, and the general concept of bounded search trees, greedy localization, and color coding.

Section 3: Bounded search trees
Description 3: Explain the method of bounded search trees as a branching algorithm technique, provide examples, and discuss its practical use.

Section 4: Greedy localization
Description 4: Detail the concept of greedy localization in parameterized algorithms, give an example, and discuss its theoretical underpinnings and practical applications.

Section 5: Color coding
Description 5: Introduce the color coding technique, explain its mechanisms, provide an example, and analyze its practical implications.

Section 6: KERNELIZATION
Description 6: Combine techniques that reduce an instance into a kernel. Differentiate between local reductions and global reductions and provide relevant examples.

Section 7: Local reductions
Description 7: Focus on reduction rules that identify and modify specific structures in an instance, proving the equivalence of the reduced instance.

Section 8: Global reduction rules-crown reduction
Description 8: Define crown decomposition and explain how it is used to reduce problem instances globally, providing examples and proofs.

Section 9: FPT BY INDUCTION
Description 9: Discuss techniques using mathematical induction for finding parameterized solutions, presenting iterative compression for minimization and the extremal method for maximization problems.

Section 10: For minimization-iterative compression
Description 10: Present the iterative compression technique suitable for parameterized minimization problems, including examples and proofs.

Section 11: For maximization-the extremal method
Description 11: Detail the extremal method for parameterized maximization problems, with examples and proofs.

Section 12: WIN/WIN
Description 12: Describe the win/win strategy, where solving an auxiliary problem helps in directly deciding the original problem, providing relevant examples.

Section 13: Well-quasi-ordering and graph minors
Description 13: Explain the concept of well-quasi-ordering and its application to parameterized problems, focusing on the role of graph minors. Include examples like the k-feedback vertex set.

Section 14: Imposing FPT structure and bounded treewidth
Description 14: Detail cases where a tree-like structure is imposed on graphs, showing that problems with bounded treewidth become solvable in FPT time. Provide an example with k-dominating set in planar graphs.