- 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 areintractable , but where it is possible to limit theexponential 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
Wikimedia Foundation. 2010.