Kernelization

In computer science, a kernelization is an efficient algorithm that preprocesses instances of decision problems by mapping them to equivalent instances with a guaranteed upper bound on the size of the output, called the kernel of the instance. Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. Being a concept of parameterized complexity theory, it is natural to give the guarantee on the size of a kernel by comparing it with a parameter associated to the problem. Indeed, kernelization can be used as a technique for creating fixed-parameter tractable algorithms.

Example: Vertex Cover

The standard example for a kernelization algorithm is the kernelization of the vertex cover problem by S. Buss. In this problem, we are given a graph $G$ and a number $k$ and we want to know whether there is a vertex cover of size $k$. This problem is NP-hard and cannot be solved in polynomial time unless P=NP. However, some easy reduction rules for this problem exist:

Rule 1. If $v$ is a vertex of degree $>k$, remove $v$ from the graph and decrease $k$ by one.

Any vertex cover of size $k$ must contain $v$ since otherwise all its neighbors would have to be picked to cover the incident edges.

Rule 2. If $v$ is an isolated vertex, remove it.

Isolated vertices cannot cover any edges and are not required for finding a vertex cover.

Rule 3. If more than $k^2$ edges remain in the graph, it cannot contain a vertex cover of size $k$.

To see this, consider a vertex cover $S$ of size $k$. Since the degree of every vertex was reduced to at most $k$ by exhaustive application of the first rule, at most $k^2$ edges are incident to $S$. On the other hand, all edges of $G$ are incident to $S$ since it is a vertex cover, so $G$ indeed has at most $k^2$ edges. Furthermore, since every vertex is either in $S$ or adjacent to $S$, the number of vertices is at most $k+k^2$. Thus, we either know that the instance is a no-instance or we end up with a graph of at most $k^2$ edges and $k+k^2$ vertices.

Kernels with fewer vertices

The most straightforward exhaustive search algorithm for the vertex cover problem runs in time roughly $2^n$, where $n$ is the number of vertices. This algorithms just tries all subsets $S\subseteq V(G)$ of the vertices and checks whether the given subset is a vertex cover. The algorithm can then check whether the graph has a vertex cover of size at most $k$.

To speed up this and more advanced exhaustive search algorithms, it is desirable to first apply an efficient kernelization algorithm to the instance and run the exhaustive search on the thus created kernel. The running time of the overall algorithm is then dominated by the number of vertices in the kernel, for which reason the goal is to come up with kernels that have as few vertices as possible. For vertex cover, kernelization algorithms are known that produce kernels with at most $2k$ vertices.

One kernelization algorithm that achieves the $2k$ vertex 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 Lampis (2011) and achieves $2k-c\log k$ vertices for any fixed constant $c$.

Kernel Lower Bounds

Given the many kernelization algorithms that exist and provide successive improvements, it is natural to ask for lower bounds on kernel sizes. Here the kernel sizes can be measured in terms of the number of vertices and in terms of the number of edges. It is suspected that the above mentioned kernelization algorithms for vertex cover are essentially optimal. In this case, kernels with $(2-\epsilon)k$ vertices or with $O(k^{2-\epsilon})$ edges cannot be produced efficiently. Recently, it has been shown that the latter would imply that coNP $\subseteq$ NP/poly, which is a statement in complexity theory that is generally believed to be false.

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 Downey & Fellows (1999), a parameterized problem is a subset $L\subseteq\Sigma^*\times\N$.

A kernelization for a parameterized problem $L$ is an algorithm that takes an instance $(x,k)$ and maps it in time polynomial in $|x|$ and $k$ to an instance $(x',k')$ such that

• $(x,k)$ is in $L$ if and only if $(x',k')$ is in $L$,
• the size of $x'$ is bounded by a function $f$ in $k$, and
• $k'$ is bounded by a function in $k$.

The output $(x',k')$ of kernelization is called a kernel. In this general context, the size of the string $x'$ 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 Flum & Grohe (2006, p. 437), a parameterized problem consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to\N$, the parameterization. The parameter of an instance $x$ is the number $\kappa(x)$.

A kernelization for a parameterized problem $L$ is an algorithm that takes an instance $x$ with parameter $k$ and maps it in polynomial time to an instance $y$ such that

• $x$ is in $L$ if and only if $y$ is in $L$ and
• the size of $y$ is bounded by a function $f$ in $k$.

Note that in this notation, the bound on the size of $y$ implies that the parameter of $y$ is also bounded by a function in $k$.

The function $f$ is often referred to as the size of the kernel. If $f=k^{O(1)}$, it is said that $L$ admits a polynomial kernel. Similarly, for $f={O(k)}$, 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 (with a computable size bound on the kernels) 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(g(k))$ for some function g, which is finite, because the problem is decidable. The total running time is $O(g(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 an 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}$.

More Examples

• Vertex Cover: The vertex cover problem has kernels with at most $2k$ vertices and $O(k^2)$ edges. Furthermore, for any $\varepsilon >0$, vertex cover does not have kernels with $O(k^{2-\varepsilon})$ edges unless $\text{coNP}\subseteq\text{NP/poly}$. The vertex cover problems in $d$-uniform hypergraphs has kernels with $O(k^{d})$ edges using the sunflower lemma, and it does not have kernels of size $O(k^{d-\varepsilon})$ unless $\text{coNP}\subseteq\text{NP/poly}$.
• Feedback Vertex Set: The feedback vertex set problem has kernels with $4k^2$ vertices and $O(k^2)$ edges. Furthermore, it does not have kernels with $O(k^{2-\varepsilon})$ edges unless $\text{coNP}\subseteq\text{NP/poly}$.
• k-Path: The k-path problem is to decide whether a given graph has a path of length at least $k$. This problem has kernels of size exponential in $k$, and it does not have kernels of size polynomial in $k$ unless $\text{coNP}\subseteq\text{NP/poly}$.
• 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.

References

• Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry; Symons, Chris T. (2004), Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments, University of Tennessee, http://www.cs.utk.edu/~langston/projects/papers/ACFLSS.pdf 
• Bodlaender, Hans L.; Downey, Rod G.; Fellows, Michael R.; Hermelin, Danny (2009), On problems without polynomial kernels, , J. Comput. Syst. Sci. 75(8): 423–434 .
• Buss, Jonathan F.; Goldsmith, Judy (1993), "Nondeterminism within P", SIAM Journal on Computing 22 (3): 560–572 
• Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001), Further Observations and Further Improvements, , J.Algorithms 41(2): 280–301 .
• Dell, Holger; van Melkebeek, Dieter (2010), "Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses", STOC 2010, pp. 251–260 .
• Downey, Rod G.; Fellows, Michael R. (1999), Parameterized Complexity, Springer, ISBN 0-387-94883-X, 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 
• Flum, Jörg; Grohe, Martin (2006), Parameterized Complexity Theory, Springer, ISBN 978-3-540-29952-3, http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0, retrieved 2010-03-05 
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and Kernels", 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503–510 .
• Lampis, Michael (2011), A kernel of order $2k-c\log k$ for vertex cover, , Information Processing Letters (Elsevier) 111 (23–24): 1089–1091, doi:10.1016/j.ipl.2011.09.003 .
• Thomassé, Stéphan (2010), A $4k^2$ kernel for feedback vertex set, , ACM Transactions on Algorithms 6(2) .
• Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms, Oxford University Press, ISBN 0-19-856607-7, http://www.oup.com/uk/catalogue/?ci=9780198566076