Problem core

In theoretical computer science designates Kernelization ( Engl . Problem kernel ) to algorithmically "difficult" decidable part of an instance of an NP-heavy problem. Many instances of NP-hard problems contain sub-problems that are easily decidable. For example, in many instances of problems where a subset S of a lot of M should be chosen elements have x of M certain properties, one by efficiently may decide that x in S must be or not in S can be.

The way to look for such items and remove them from the instance to, is called Kernelization reduction ( Engl . Nuclear Eliza tion ). The elements that do not have such properties and are left after problem core reductions form the problem core of the instance.

Examples

In instances G of the q -coloring problem , successive nodes x can be removed whose degree is smaller than q , because in a q -coloring of the residual graph the neighborhood of x contains at most q-1 colors, leaving at least one color for x . As a result, G is q -colourable if and only if the graph G ' , which results from G after removing the node x , is q -colourable.

In the case of instances (G, k) of the parameterized node coverage problem (i.e. when searching for a node coverage of size k ), one can choose successive nodes x whose degree is greater than k . These have to be part of the node coverage, because the edges that are incident to x have to be covered, for which otherwise only the entire neighborhood of x would come into question. However, this would be more than k nodes, which would immediately exceed the limit for the size of the node coverage. As a result, G has a node coverage of the size if and only if Gx has a node coverage of the size . ${\ displaystyle \ leq k}$ ${\ displaystyle \ leq k-1}$

In instances G of the q -clique problem , successive nodes x can be removed whose degree is less than q-1 , because the nodes of a q -clique are adjacent to the other q-1 nodes of the clique, from which a degree of at least for these nodes q-1 follows. This means that G has a q -clique if and only if Gx has a q -clique.

The assumed problem need not necessarily be decidable or semi-decidable . For example, the removal of unreachable states of a Turing machine also corresponds to the definition of a problem core reduction for the (not semi-decidable) question of whether the Turing machine calculates a partial function .

Formal definition

Be a parameterized problem with a norm on . ${\ displaystyle P \ subseteq M \ times \ mathbb {N}}$ ${\ displaystyle |. |}$ ${\ displaystyle M}$

A problem core reduction is a function with the properties ${\ displaystyle f \ colon M \ times \ mathbb {N} \ rightarrow M \ times \ mathbb {N}}$

${\ displaystyle (I, k) \ in P \ Leftrightarrow (I ^ {\ prime}, k ^ {\ prime}): = f (I, k) \ in P}$ (Equivalence)
${\ displaystyle | I ^ {\ prime} | \ leq | I |}$ and (simplification) ${\ displaystyle k ^ {\ prime} \ leq k}$
f can be calculated in polynomial time

Kernelization reductions each define a transitive , well-founded order relation R on . A problem core of an instance (I, k) is an R -normal of (I, k) with respect to a problem core reduction relation R . Problem core reductions are often confluent , which means that their normal forms are then unambiguous. This is why one often speaks of “the” problem core of an instance, ignoring the fact that other (possibly still unknown) problem core reductions could lead to even smaller instances. ${\ displaystyle M \ times \ mathbb {N}}$

Upper bounds on size

Every decidable, parameterized problem for which one can guarantee that the size of the problem kernel of each instance (I, k) is limited by g (k) , for any function g , is fixed parameter tractable , since after a problem kernel reduction can apply an algorithm with any (finite) running time h to the problem core, which results in a running time of . ${\ displaystyle poly (n) + h (g (k))}$

Conversely, every instance (I, k) of a problem that is fixed parameter tractable has a problem core that can be calculated in polynomial time and whose size is limited by g (k) for a function g . Proof sketch: Given is a parameterized problem that is fixed parameter tractable, for which there is an algorithm that solves every instance (I, k) with a running time of . A problem kernel reduction is now: if | I | <f (k) , then (I, k) is itself a suitable problem kernel (the size of which is limited by f (k) ). Otherwise the FPT algorithm can be used to determine whether is. Based on this, one chooses as the problem core any (but fixed) instance or , with which the size of each problem core is limited by . The decisive factor here is: In the case that f (k) <| I | is the running time of the algorithm , with which the polynomial running time follows. ${\ displaystyle f (k) | I | ^ {c}}$ ${\ displaystyle (I, k) \ in P}$ ${\ displaystyle I _ {\ text {yes}} \ in P}$ ${\ displaystyle I _ {\ text {no}} \ not \ in P}$ ${\ displaystyle g (k): = \ max \ {f (k), | I _ {\ text {yes}} |, | I _ {\ text {no}} | \}}$ ${\ displaystyle f (k) | I | ^ {c} \ leq | I | ^ {c + 1}}$

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

Nevertheless, even with problems that are not fixed parameter tractable, i.e. where it cannot be guaranteed that the problem core is relatively small, it makes sense to apply problem core reductions at the beginning of each recursion call, since in practice they also result in major improvements in runtimes bring.

Finer gradation of FPT

The different bounds for the size of the problem core provide a finer gradation of the complexity class FPT. For example, the node coverage problem is "easier" than the Min-Multicut problem on trees, although both are in FPT, because the problem core of an instance of the node coverage problem (according to Nemhauser and Trotter) is at most 2k , whereas the best known problem core reduction for Min -Multicut on trees delivers problem kernels whose size is limited by . Both are in the important class POLYKERNEL , which contains the problems whose instances have problem kernels whose size is limited by a polynomial in k . ${\ displaystyle k ^ {6}}$

literature

Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms . Oxford University Press, Oxford 2006, ISBN 0-19-856607-7 , ( Oxford Lecture Series in Mathematics and its Applications 31).