Kernelization

In computer science, kernelization is a technique for creating algorithms for fixed-parameter tractable problems. Given some language L, the input to a fixed-parameter tractable problem is a pair $(x,\; k)$ where x is a word from L and k is an integer, called the parameter. Fixed-parameter tractability is used for problems that are intractable, but where it is possible to limit the exponential part of the runtime to some parameter k, such that the total time becomes $f(k)\; *\; |x|^\{O(1)\}$, where the function f only depends on k, and not on the size of x.

Definition

The idea of kernelization is to reduce the size of the input x to a function of k in polynomial time. When the input is bounded by k, we can use any exponential time algorithm, for example brute-force search, to find the solution. We say that a problem is kernelizable if there is a kernelization algorithm for it. More formally, a language L is kernelizable if there exists a polynomial-time algorithm that on input (x, k) creates an output (x', k') such that (x, k) is in L if and only if (x', k') is in L, and further that k' is upper bounded by a function of k and the size of x' is upper bounded by a function of k'.

Kernelization and fixed-parameter tractability

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. Use the kernelization algorithm, which uses $O(|x|^c)$ time for some c, and then solve the output from the kernelization in time $O(d^k)$ for some d. The total running time is $O(d^k\; *\; |x|^c)$. The other direction, that a fixed-parameter tractable problem is kernelizable and decidable is a bit more involved. We will assume that the question is non-trivial, such that there is at least one instance that is in the language, called $I\_\{yes\}$, and at least one instance that is not in the language, called $I\_\{no\}$. Assume the input is (x, k), and that there exists and algorithm that runs in time $f(k)*|x|^c$. We will now construct a kernelization algorithm, by finding in polynomial time an instance (x', k) where x' is bounded by k. If the size of x is less than f(k) we can just return (x, k). Otherwise, run the algorithm that proves the problem is fixed-parameter tractable and if the answer is yes, return $I\_\{yes\}$, otherwise return $I\_\{no\}$. The latter is ok because when $|x|\; geq\; f(k)$, we get also that $f(k)\; cdot\; |x|^c\; leq\; |x|^\{c+1\}$.

Further reading

*R. G. Downey, Michael R. Fellows, Ulrike Stege. [http://citeseer.ist.psu.edu/downey97parameterized.html Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability] .
* Faisal N. Abu-Khzam et al. [http://www.cs.utk.edu/~langston/projects/papers/ACFLSS.pdf Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments] .

References

*cite book
first=Rod
last=Downey
coauthors=M. Fellows
title=Parameterized complexity
publisher=Springer
year=1999
url=http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X
isbn = 0-387-94883-X
*cite
author = Faisal N. Abu-Khzam
coauthors = Rebecca L. Collins and Michael R. Fellows and Michael A. Langston and W. Henry Suters and Chris T. Symons
title = Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments
date = 2004
publisher = University of Tennessee
url = http://www.cs.utk.edu/~langston/projects/papers/ACFLSS.pdf