Kernelization
In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. In parameterized  complexity theory, it is often possible to prove that a kernel with guaranteed bounds on the size of a kernel (as a function of some parameter associated to the problem) can be found in polynomial time. When this is possible, it results in a fixed-parameter tractable algorithm whose running time is the sum of the (polynomial time) kernelization step and the (non-polynomial but bounded by the parameter) time to solve the kernel. Indeed, every problem that can be solved by a fixed-parameter tractable algorithm can be solved by a kernelization algorithm of this type. Example: vertex cover . A standard example for a kernelization algorithm is the kernelization of the vertex cover problem by S. Buss. In this problem, the input is an undirected graph formula_1 together with a number formula_2. The output is a set of at most formula_2 vertices that includes an endpoint of every edge in the graph, if such a set exists, or a failure exception if no such set exists. This problem is NP-hard. However, the following reduction rules may be used to kernelize it: An algorithm that applies these rules repeatedly until no more reductions can be made necessarily terminates with  a kernel that has at most formula_14 edges and (because each edge has at most two endpoints and there are no isolated vertices) at most formula_22 vertices. This kernelization may be implemented in linear time. Once the kernel has been constructed, the vertex cover problem may be solved by a brute force search algorithm that tests whether each subset of the kernel is a cover of the kernel. Thus, the vertex cover problem can be solved in time formula_23 for a graph with formula_24 vertices and formula_25 edges, allowing it to be solved efficiently when formula_2 is small even if  formula_24 and formula_25 are both large. Although this bound is fixed-parameter tractable, its dependence on the parameter is higher than might be desired. More complex kernelization procedures can improve this bound, by finding smaller kernels, at the expense of greater running time in the kernelization step. In the vertex cover example, kernelization algorithms are known that produce kernels with at most formula_29 vertices. One algorithm that achieves this improved bound exploits the half-integrality of the linear program relaxation of vertex cover due to Nemhauser and Trotter. Another kernelization algorithm achieving that bound is based on what is known  as the crown reduction rule and uses alternating path arguments. The currently best known kernelization algorithm in terms of the number of vertices is due to and achieves formula_30 vertices for any fixed constant formula_31. It is not possible, in this problem, to find a kernel of size formula_32, unless P = NP, for such a kernel would lead to a polynomial-time algorithm for the NP-hard vertex cover problem. However, much stronger bounds on the kernel size can be proven in this case: unless coNP formula_33 NP/poly (believed unlikely by complexity theorists), for every formula_34 it is  impossible in polynomial time to find kernels with formula_35 edges. It is unknown for vertex cover whether kernels with formula_36 vertices for some formula_34 would have any unlikely complexity-theoretic consequences. Definition. In the literature, there is no clear consensus on how kernelization should be formally defined and there are subtle differences in the uses of that expression. Downey–Fellows notation. In the notation of , a "parameterized problem" is a subset formula_38 describing a decision problem. A kernelization for a parameterized problem formula_39 is an algorithm that takes an instance formula_40 and maps it in time polynomial in formula_41 and  formula_2 to an instance formula_43 such that The output formula_43 of kernelization is called a kernel. In this general context, the "size" of the string formula_48 just refers to its length. Some authors prefer to use the number of vertices or the number of edges as the size measure in the context of graph problems. Flum–Grohe notation. In the notation of , a "parameterized problem" consists of a decision problem formula_55 and a function formula_56, the parameterization. The "parameter" of an instance formula_57 is the number formula_58. A kernelization for a parameterized problem formula_39 is an algorithm that takes an  instance formula_57 with parameter formula_2 and maps it in polynomial time to an instance formula_62 such that Note that in this notation, the bound on the size of formula_62 implies that the parameter of formula_62 is also bounded by a function in formula_2. The function formula_49 is often referred to as the size of the kernel. If formula_74, it is said that formula_39 admits a polynomial kernel. Similarly, for formula_76, the problem admits linear kernel. Kernelizability and fixed-parameter tractability are equivalent. A problem is fixed-parameter tractable if and only if it is kernelizable and decidable. That a kernelizable  and decidable problem is fixed-parameter tractable can be seen from the definition above: First the kernelization algorithm, which runs in time formula_77 for some c, is invoked to generate a kernel of size formula_78. The kernel is then solved by the algorithm that proves that the problem is decidable. The total running time of this procedure is formula_79, where formula_80 is the running time for the algorithm used to solve the kernels. Since formula_81 is computable, e.g. by using the assumption that formula_78 is computable and testing all possible inputs of length formula_78, this implies that the problem is  fixed-parameter tractable. The other direction, that a fixed-parameter tractable problem is kernelizable and decidable is a bit more involved. Assume that the question is non-trivial, meaning that there is at least one instance that is in the language, called formula_84, and at least one instance that is not in the language, called formula_85; otherwise, replacing any instance by the empty string is a valid kernelization. Assume also that the problem is fixed-parameter tractable, i.e., it has an algorithm that runs in at most formula_86 steps on instances formula_87, for some constant formula_31 and some function formula_78 . To kernelize an input, run this algorithm on the given input for at most formula_90 steps. If it terminates with an answer, use that answer to select either formula_84 or formula_85 as the kernel. If, instead, it exceeds the formula_90 bound on the number of steps without terminating, then return formula_40 itself as the kernel. Because formula_40 is only returned as a kernel for inputs with formula_96, it follows that the size of the kernel produced in this way is at most formula_97. This size bound is computable, by the assumption from fixed-parameter tractability that formula_78 is computable. Kernelization  for structural parameterizations. While the parameter formula_2 in the examples above is chosen as the size of the desired solution, this is not necessary. It is also possible to choose a structural complexity measure of the input as the parameter value, leading to so-called structural parameterizations. This approach is fruitful for instances whose solution size is large, but for which some other complexity measure is bounded. For example, the "feedback vertex number" of an undirected graph formula_1 is defined as the minimum cardinality of a set of vertices whose removal makes formula_1 acyclic. The vertex cover problem parameterized by  the feedback vertex number of the input graph has a polynomial kernelization: There is a polynomial-time algorithm that, given a graph formula_1 whose feedback vertex number is formula_2, outputs a graph formula_123 on formula_124 vertices such that a minimum vertex cover in formula_123 can be transformed into a minimum vertex cover for formula_1 in polynomial time. The kernelization algorithm therefore guarantees that instances with a small feedback vertex number formula_2 are reduced to small instances.