↑ arvau

Wikipedia / 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. This is also true for approximate kernelization.

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 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:

  1. back to the cover.

  2. cannot be part of any minimal cover.

  3. , which also has no solution.

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 are both large.

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 .

, 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 NP/poly (believed unlikely by complexity theorists edges. 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 describing a decision problem.

A kernelization such that

of kernelization is called a kernel. In this general context, the size 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, the parameterization. The parameter.

A kernelization such that

  • and

  • .

.

, 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.

, this implies that the problem is fixed-parameter tractable.

; otherwise, replacing any instance by the empty string is computable.

More examples

  • Vertex cover parametrized by the size of the vertex cover: The vertex cover edges.. edges using the sunflower lemma.

  • Feedback vertex set parametrized by the size of the feedback vertex set: The feedback vertex set edges..

  • -path:-path problem is to decide whether a given graph has a path.

  • Bidimensional problems: Many parameterized versions of bidimensional problems have linear kernels on planar graphs, and more generally, on graphs excluding some fixed graph as a minor.

Kernelization for structural parameterizations

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 acyclic. The vertex cover problem parameterized by the feedback vertex number of the input graph has a polynomial kernelization: are reduced to small instances.

See also

Notes

References

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • .

  • ,

  • .

  • .

  • .

Further reading