An Overview of Techniques for Designing Parameterized Algorithms <s> For maximization-the extremal method <s> 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. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> For maximization-the extremal method <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> BIB002
For maximization problems we consider smaller instances of the type (G, k 2 1), and induct on k instead of n. We say that a problem is parameter monotone if the 'No'-instances are closed under parameter increment, i.e. if instance (G, k) is a 'No'-instance then (G, k 0 ) is also a 'No'-instance for all k 0 . k. For a parameter monotone problem, we can modify the meta-algorithm from the previous section to obtain an inductive algorithm for maximization problems. (see Fig. 13 ). The Method of Extremal Structure 5 is a design technique that works well for parameter monotone maximization problems. In this technique, we do not focus on any particular instance (G, k), but instead investigate the structure of graphs that are 'Yes'-instances for k, but 'No'-instances for k þ 1. Let G(k) be the class of such graphs, i.e. Our ultimate goal is to prove that there exists a function f(k) such that maxfjV(G)j jG [ G(k)g f(k). This is normally not possible without some refinement of G(k), to do this we make a set of observations E of the following type: Given a set of such observations E and consequently a set of properties P we try to devise a set of reduction rules R that apply specifically to large graphs having the properties P. We call our refined class G R (k) ¼ fGj no reduction rule in R applies to (G, k), and (G, k) is a 'Yes'-instance, and (G, k þ 1) is a 'No'-instanceg. If we can add enough observations to E and reductions rules to R to prove that there is a function f(k) such that max fjV(G)j jG [ G R (k)g f(k) we have proven that: Given such a boundary lemma and the fact that the problem is a parameter monotone maximization problem a kernelization lemma follows, saying that if no rule in R applies to (G, k) and jV(G)j . f(k), then (G, k) is a 'Yes'-instance. It is not immediately obvious that this can be viewed as an inductive process, but we will now make this clear by presenting the Algorithmic Method, a version of the 'Extremal FIGURE 13: a meta-algorithm for parameter monotone problems BIB001 An exposition of this design technique can be found in Prieto's PhD thesis BIB002 .