An Overview of Techniques for Designing Parameterized Algorithms <s> Greedy localization <s> 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. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> Greedy localization <s> 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). <s> BIB002
Greedy localization is a technique that uses a clever first branching to start off the recursive search for the solution. It was introduced in BIB001 BIB002 and popularized in an IWPEC'04 paper  . Our aim is to show that if a parameterized problem satisfies the following conditions then greedy localization will give an FPT algorithm. (1) The problem can be formulated as that of finding k pairwise non-overlapping 'objects' in an input instance G, with objects being special subsets of size depending only on k of a ground set W of G. (2) For any R#W and X#W we can decide in FPT time if there exists S#W \ X such that S < R is an object. Not all bounded-size subsets of W are objects, and an obvious requirement for the problem to have an FPT algorithm is that for any R#W we must be able to decide in FPT time if R is an object or not. Condition 2 can be seen as a strengthening of this obvious requirement and we will refer to S as an 'extension' of the 'partial object' R to a 'full object' R < S avoiding X. Figure 4 gives the greedy localization algorithm, in nondeterministic style, for a problem satisfying these two conditions. It uses the notation that for a set of partial objects B ¼ fB 1 , B 2 , . . . , B k g the ground elements contained in B are denoted by W B ¼ > B i [B B i . THEOREM 1. If a parameterized problem satisfies conditions 1 and 2 above then the algorithm 'greedy localization' is an FPT algorithm for this problem. Proof. The algorithm starts by computing an inclusion maximal non-overlapping set of objects A. By condition 2 this first step can be done in FPT time as follows: repeatedly extend the emptyset to a full object while avoiding a set X, by calling subroutine EXTEND(1, X) with X initially empty, and adding the extension to X before the next iteration. When no extension exists we are assured that the sequence of extensions found must be an inclusion maximal nonoverlapping set of objects A. The crucial aspect that makes the algorithm correct is that if A and B are two inclusion maximal non-overlapping sets of objects then for any object B i in B there is an object A j in A such that A j and B i overlap, since otherwise A is not maximal. Thus, if the instance contains such a set B of at least k objects, then we can guess k ground elements appearing in A, with A constructed in the first step of the algorithm, such that these ground elements belong to k separate objects of B. The branching subroutine is called on these k one-element partial objects and we greedily try to extend them to full objects. If this fails for some object B j , after having added extension elements F to objects B 1 , B 2 , . . . , B j21 , then there must exist an element v from F that should have instead been used to extend B j . We then simply guess the element v and try again. For a deterministic algorithm, the guesses are replaced by branchings, and we give a No answer iff all branches answer No. The first branching is of size jW A j k , the remainder of the branches are of size jFj, and the total height of the tree is bounded by k times the maximum size of an object since at each level one new ground element is added to W B . All these are bounded by a function depending on k as we assumed in condition 1 that each object had size depending on k only. The calls to the extend subroutine are FPT by condition 2. Hence the algorithm is FPT. A 2.2.1. Example: k-packing of k-cycles Using Theorem 1, we can easily argue that deciding if a graph G contains k vertex-disjoint cycles on k vertices is FPT by greedy localization. The ground set W will be the vertex set of G and the objects will be subsets of k vertices inducing a subgraph containing a k-cycle, to satisfy condition 1. Given R, X#W we can by an FPT algorithm designed using the Color Coding technique, see the next section, decide if there exists S#W \ X such that R < S induces a subgraph containing a k-cycle, to satisfy condition 2. By Theorem 1 the greedy localization meta-algorithm therefore solves the problem in FPT time. For packing of edge-disjoint cycles, a similar argument holds with W being the edge set of the graph.