Kernelization

In theoretical computer science the core problem ( engl. problem kernel) identifies the algorithmically " difficult " decidable part of an instance of an NP- Hard problem. Many instances of NP- hard problems contain sub-problems that are easily decidable. For example, in many instances of problems in which a subset of S is to be chosen from a set M x M elements have certain properties by which one can decide efficiently that x be in S must or can not be in S.

The way to look for such items and remove them from the instance is called a problem kernel reduction ( engl. core Eliza -tion ). The elements, which do not have such properties and are left on the problem core reduction, forming the core of the problem instance.

Examples

For instances, G q- coloring problem successive node x can be removed, the degree of which is smaller than q, because in a q- coloring of the remaining graph, the neighborhood of x more than q-1 contains colors which at least one color is left for x. Thus G is q -colourable if the graph G ', the x results from G after removal of the node is q- colorable.

For instances (G, k) of the parameterized vertex cover problem ( ie, finding a vertex cover of size k ) one can successively select node x whose degree is greater than k. This must be part of the vertex cover, because that must be covered to x incident edges, for which otherwise only would the entire neighborhood of x in question. But this would be more than k nodes, which immediately the limit would be exceeded for the size of the vertex cover. Thus G has exactly then a vertex cover of size, if Gx has a vertex cover of size.

In instances G of the q- clique problem successively node x can be removed whose degree is less than q -1, because the nodes of a q- clique are adjacent with the other q-1 vertices of, resulting for these nodes a level of at least q -1 is followed. Thus G has exactly then a q- clique if Gx has a q- clique.

The presumed problem must be not necessary decidable or semi- decidable. For example, the removal of unreachable states of a Turing machine corresponds to the definition of a core problem - reduction for the ( not semi- decidable ) whether the Turing machine computes a partial function.

Formal definition

Be a parameterized problem with a standard.

A core problem reduction is a function with the properties of # (equivalence ) and # ( simplification ) # f is computable in polynomial

Problem nuclear reductions each define a transitive, well- founded ordering relation R. A core problem of an instance (I, k) is an R- normal form of (I, k) with respect to a problem kernel reduction relation R. Problem nuclear reductions are often confluent, reducing their normal forms are then clear. Therefore, one often speaks also of " the " core problem of an instance, but they does not take into that other (possibly unknown ) could cause core problem reductions even smaller instances.

Upper bounds for the size

Every decidable parameterized problem for which one can guarantee that the size of the problem, the core of each instance (I, k ) is bounded by g ( k) for any function g, is fixed parameter tractable, because you after a problem kernel reduction may apply an algorithm with an arbitrary ( finite ) duration h on the core problem, thus resulting in a term of.

Conversely, any instance (I, k) of a problem fixed parameter tractable is a problem core, which is computable in polynomial time and its size is limited by g ( k), for a function g Proof sketch: Given a parameterized problem the fixed parameter tractable is, for so exists an algorithm with a running time of solves each instance (I, k). A core problem - reduction is: if | I | < f ( k), then ( I, k ) itself, a suitable core problem (whose size is bounded by f ( k)). Otherwise, you can use the FPT algorithm to determine whether. Based on this, is chosen as the core problem an arbitrary (but fixed chosen ) or instance, so that the size of each core problem is limited by. Here it is crucial: In the case that f ( k) <| I |, is the running time of the algorithm, thus the polynomial running time follows.

So it turns out that the complexity class FPT corresponds exactly to the class of parameterized problems whose problem kernels are limited by a function of the parameter.

Nevertheless, it is also for problems fixed parameter tractable are not, so where there is no guarantee that the problem core is relatively small, meaningful, problem -core reductions at the beginning of use of each Rekursionsaufrufs, since in practice there too big improvements in running times bring.

Finer gradation of FPT

The different bounds on the size of the problem that core a finer gradation of the complexity class FPT. For example, the vertex cover problem "easier" than the Min- Multicut Problem on trees, although both are in FPT, because the problem nucleus of an instance of the vertex cover problem has 2k maximum size ( by Nemhauser and Trotter ), whereas the best known problem of core reduction for Min - Multicut on trees problem provides nuclei whose size is limited by. Both, however, are located in the important class POLYKERNEL containing the problems whose instances have problem nuclei whose size is bounded by a polynomial in k.