An Overview of Techniques for Designing Parameterized Algorithms <s> DEFINITION 2. <s> 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. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> DEFINITION 2. <s> 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. <s> BIB002 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> DEFINITION 2. <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> BIB003 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> DEFINITION 2. <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> BIB004
A crown decomposition of a graph G ¼ (V, E) is a partitioning of V into sets C,H,R, where C and H are both non-empty, such that: (1) C is an independent set. When using a crown decomposition (C, H, R) in a reduction rule for a graph G we usually show that we can remove or modify (C < H) to obtain a reduced instance (G 0 , k 0 ) which is a Yes-instance if and only if (G, k) is a Yes-instance. For example, it is easy to see that G has a vertex cover of size k iff the graph G 0 resulting from removing C < H has a vertex cover of size k 2 jHj. Usually, more complicated reduced instances and arguments are necessary. For example, an FPT algorithm for k-internal spanning tree BIB004 uses crown reduction rules that remove only the vertices of C not incident to a matched edge. Although it is possible to determine if a graph has a crown decomposition in polynomial time  , this technique is often combined with the following lemma by Chor et al. BIB003 . LEMMA 1. If a graph G ¼ (V, E) has an independent set I such that jN(I)j , jIj, then a crown decomposition (C,H,R) for G such that C#I can be found in time O(jVj þ jEj). The notation N(I) denotes vertices in V \ I that are adjacent to a vertex in I. Since it is W[1]-hard to find a large independent set we cannot directly apply Lemma 1. To see how the lemma can be used, we consider k-vertex cover on a graph G in the next section. Although crown reduction rules were independently discovered by Chor et al. BIB003 one should note that a similar type of structure has been studied in the field of boolean satisfiability problems (SAT). An autarky is a partial truth assignment (assigning true/false to only a subset of the variables) such that each clause that contains a variable determined by the partial truth assignment is satisfied. In a matching autarky, we require in addition that the clauses satisfied and the satisfying variables form a matching cover in the natural bipartite graph description of the SAT. It is easy to see that the matching autarky is a crown decomposition in this bipartite graph. The main protagonist in this field is Kullmann BIB001 BIB002 , who has developed an extensive theory on different types of autarkies.