An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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. <s> BIB002 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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) . <s> BIB003 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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. <s> BIB004 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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. <s> BIB005 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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). <s> BIB006 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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). <s> BIB007 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <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> BIB008 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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]. <s> BIB009 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> How is it used in practice? <s> 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. <s> BIB010
This is arguably the most successful parameterized algorithm design technique. The powerful k-vertex cover algorithm by Chen, et al. BIB001 , running in time O (1.286 k n), is a bounded search tree algorithm and remains one of the most cited results in the field. Also for practical implementations bounded search tree algorithms remain one of the best design techniques, achieving very good running times (M. Langston, Personal Communication). However, we would like to note that the effectiveness of a practical implementation of a bounded search tree algorithm may be dependent on the number of cases then the algorithm attempts. If the algorithm checks for just a handful of cases, then the running time of the algorithm is usually low, and its implementation feasible. However, there are cases in the literature where the number of cases reach the tens of thousands  . Although this allows for very good theoretical performance the unavoidable overhead will slow down any practical implementation. Some very good implementations of the vertex cover algorithm deliberately skip some of the more advanced cases as they in most practical instances only slow the algorithm down, as reported in (M. Langston, Personal Communication). A graph G with vertex a having 3 neighbors, and two levels of the bounded search trees for k-independent set in planar graphs and for k-vertex cover. Any maximal independent set will contain either vertex a or at least one of its neighbors, while any vertex cover will contain either vertex a or all three neighbors  Since we do not know of any practical implementation of this technique we simply give our opinion on the practical usefulness of this design technique. Observe that the running time of this algorithm depends on the running time of the EXTEND subroutine and the maximum size of the objects. The size of objects determine the size of our branching tree and also the number of times the EXTEND subroutine is executed. This, together with the inherent running time of O*(c k log k ), lead us to believe that greedy localization is impractical for anything but small constant sized objects. Perhaps the strongest theoretical results using color coding are obtained in BIB004 where it is combined with kernelization to give FPT algorithms for a large variety of packing problems. In general, a major drawback of these algorithms is that while the hash family has an asymptotically good size, the O-notation hides a large constant. Thus, from a practical viewpoint the color coding algorithms would for reasonable input sizes normally be slower than a 2 k log k algorithm obtained through other techniques. We believe that this algorithm design technique is unsuitable in practice. The idea of pre-processing an input forms a heuristic for many real-world problems. Kernelization is a sibling of this idea where we have a guarantee on its effectiveness. It can can be extremely useful in practical implementations as it allows for a fast reduction of the input size. For many instances, the reduction rules work much better than the worst case analysis would indicate BIB002 . Crown decompositions have been used with great success in the vertex cover problem. Although it does not always reach as good kernel as the competitive linear programming or network flow algorithms it uses only a fraction of the time and it is often worth using a crown reduction rule as a preprocessing for the more time consuming methods, as reported by implementations in  . The general practical effectiveness of this design technique depends directly on how well the induction step can be implemented. For the vertex cover problem above we use an effective crown reduction algorithm and thus the accompanying algorithm would run well in practice. We hope that the implementations testing this technique in practice will appear soon. This technique, either the 'Extremal Method' or its variant the 'Algorithmic Method', has been applied successfully to a range of problems, such as: k-max Cut BIB007 , k-leaf spanning tree BIB008 , k-non-blocker BIB008 , k-edge-disjoint triangle-packing BIB005 , k-K 1,s -packing BIB006 , k-K 3 -packing  , k-set splitting BIB003 and k-internal spanning tree BIB009 . We do not know of any practical implementation of algorithms of this type, but the kernelization results that can be obtained from 'Extremal Method' argumentation is generally quite good. This, together with the general simplicity of the technique, indicates that the technique could be successful in practice. Although its extreme simplicity makes the technique very useful as a method for proving membership in FPT, the number of forbidden minors is often quite large and even worse, usually unknown. Thus, this technique is rarely viable as a tool for designing practical algorithms. According to BIB010 the only known algorithms with subexponential running time O*(c p k ) are algorithms based on imposing treewidth and branchwidth structure on the complicated cases, and these fall into the win/win category. We cannot say much about the practical usefulness of this design technique in general. The running time of a win/win algorithm depends on two things: the nature of the observation that ties one problem to another, and the running time to solve the other problem. Normally the observation can be checked in polynomial time, but to have a practical implementation it must also give a reasonable parameter value for the other problem.