Kernelization

Last updated January 04, 2024

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.^[1] In this problem, the input is an undirected graph $G$ together with a number $k$ . The output is a set of at most $k$ 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:

If $k>0$ and $v$ is a vertex of degree greater than $k$ , remove $v$ from the graph and decrease $k$ by one. Every vertex cover of size $k$ must contain $v$ since otherwise too many of its neighbors would have to be picked to cover the incident edges. Thus, an optimal vertex cover for the original graph may be formed from a cover of the reduced problem by adding $v$ back to the cover.
If $v$ is an isolated vertex, remove it. An isolated vertex cannot cover any edges, so in this case $v$ cannot be part of any minimal cover.
If more than $k^{2}$ edges remain in the graph, and neither of the previous two rules can be applied, then the graph cannot contain a vertex cover of size $k$ . For, after eliminating all vertices of degree greater than $k$ , each remaining vertex can only cover at most $k$ edges and a set of $k$ vertices could only cover at most $k^{2}$ edges. In this case, the instance may be replaced by an instance with two vertices, one edge, and $k=0$ , which also has no solution.

An algorithm that applies these rules repeatedly until no more reductions can be made necessarily terminates with a kernel that has at most $k^{2}$ edges and (because each edge has at most two endpoints and there are no isolated vertices) at most $2k^{2}$ 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 algorithm that tests whether each subset of the kernel is a cover of the kernel. Thus, the vertex cover problem can be solved in time $O(2^{2k^{2}}+n+m)$ for a graph with $n$ vertices and $m$ edges, allowing it to be solved efficiently when $k$ is small even if $n$ and $m$ are both large.

Although this bound is fixed-parameter tractable, its dependence on the parameter is higher than might be desired. More complex kernelization procedures can improve this bound, by finding smaller kernels, at the expense of greater running time in the kernelization step. In the vertex cover example, kernelization algorithms are known that produce kernels with at most $2k$ 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.^[2] Another kernelization algorithm achieving that bound is based on what is known as the crown reduction rule and uses alternating path arguments.^[3] 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$ .

It is not possible, in this problem, to find a kernel of size $O(\log k)$ , 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 $\subseteq$ NP/poly (believed unlikely by complexity theorists), for every $\epsilon >0$ it is impossible in polynomial time to find kernels with $O(k^{2-\epsilon })$ edges.^[4] It is unknown for vertex cover whether kernels with $(2-\epsilon )k$ vertices for some $\epsilon >0$ 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 Downey & Fellows (1999), a parameterized problem is a subset $L\subseteq \Sigma ^{*}\times \mathbb {N}$ describing a decision problem.

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 computable 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. 4), a parameterized problem consists of a decision problem $L\subseteq \Sigma ^{*}$ and a function ${\displaystyle \kappa$ , 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 computable 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 and decidable.

That a kernelizable and decidable problem is fixed-parameter tractable can be seen from the definition above: First the kernelization algorithm, which runs in time $O(|x|^{c})$ for some c, is invoked to generate a kernel of size $f(k)$ . The kernel is then solved by the algorithm that proves that the problem is decidable. The total running time of this procedure is $g(f(k))+O(|x|^{c})$ , where $g(n)$ is the running time for the algorithm used to solve the kernels. Since $g(f(k))$ is computable, e.g. by using the assumption that $f(k)$ is computable and testing all possible inputs of length $f(k)$ , this implies that the problem is fixed-parameter tractable.

The other direction, that a fixed-parameter tractable problem is kernelizable and decidable is a bit more involved. Assume that the question is non-trivial, meaning 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}$ ; otherwise, replacing any instance by the empty string is a valid kernelization. Assume also that the problem is fixed-parameter tractable, i.e., it has an algorithm that runs in at most $f(k)\cdot |x|^{c}$ steps on instances $(x,k)$ , for some constant $c$ and some function $f(k)$ . To kernelize an input, run this algorithm on the given input for at most $|x|^{c+1}$ steps. If it terminates with an answer, use that answer to select either $I_{yes}$ or $I_{no}$ as the kernel. If, instead, it exceeds the $|x|^{c+1}$ bound on the number of steps without terminating, then return $(x,k)$ itself as the kernel. Because $(x,k)$ is only returned as a kernel for inputs with $f(k)\cdot |x|^{c}>|x|^{c+1}$ , it follows that the size of the kernel produced in this way is at most $\max\{|I_{yes}|,|I_{no}|,f(k)\}$ . This size bound is computable, by the assumption from fixed-parameter tractability that $f(k)$ is computable.

More examples

Vertex cover parametrized by the size of the vertex cover: The vertex cover problem has kernels with at most $2k$ vertices and $O(k^{2})$ edges.^[5] Furthermore, for any $\varepsilon >0$ , vertex cover does not have kernels with $O(k^{2-\varepsilon })$ edges unless ${\text{coNP}}\subseteq {\text{NP/poly}}$ .^[4] 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}}$ .^[4]
Feedback vertex set parametrized by the size of the feedback vertex set: The feedback vertex set problem has kernels with $4k^{2}$ vertices and $O(k^{2})$ edges.^[6] Furthermore, it does not have kernels with $O(k^{2-\varepsilon })$ edges unless ${\text{coNP}}\subseteq {\text{NP/poly}}$ .^[4]
$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}}$ .^[7]
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.^[8]

Kernelization for structural parameterizations

While the parameter $k$ 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 of an undirected graph $G$ is defined as the minimum cardinality of a set of vertices whose removal makes $G$ acyclic. The vertex cover problem parameterized by the feedback vertex number of the input graph has a polynomial kernelization:^[9] There is a polynomial-time algorithm that, given a graph $G$ whose feedback vertex number is $k$ , outputs a graph $G'$ on $O(k^{3})$ vertices such that a minimum vertex cover in $G'$ can be transformed into a minimum vertex cover for $G$ in polynomial time. The kernelization algorithm therefore guarantees that instances with a small feedback vertex number $k$ are reduced to small instances.

Notes

↑ This unpublished observation is acknowledged in a paper of Buss & Goldsmith (1993)
↑ Flum & Grohe (2006)
↑ Flum & Grohe (2006) give a kernel based on the crown reduction that has $3k$ vertices. The $2k$ vertex bound is a bit more involved and folklore.
1 2 3 4 Dell & van Melkebeek (2010)
↑ Chen, Kanj & Jia (2001)
↑ Thomassé (2010)
↑ Bodlaender et al. (2009)
↑ Fomin et al. (2010)
↑ Jansen & Bodlaender (2013)

Related Research Articles

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In the parameterized complexity of algorithms, the klam value of a parameterized algorithm is a number that bounds the parameter values for which the algorithm might reasonably be expected to be practical. An algorithm with a higher klam value can be used for a wider range of parameter values than another algorithm with a lower klam value. The klam value was first defined by Downey and Fellows (1999), and has since been used by other researchers in parameterized complexity both as a way of comparing different algorithms to each other and in order to set goals for future algorithmic improvements.

In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step.

<span class="mw-page-title-main">Nonblocker</span> Subgraph

In graph theory, a nonblocker is a subset of vertices in an undirected graph, all of which are adjacent to vertices outside of the subset. Equivalently, a nonblocker is the complement of a dominating set.

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices and includes every edge connecting any two vertices in the subset.

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.

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 (PDF), University of Tennessee.
Bodlaender, Hans L.; Downey, Rod G.; Fellows, Michael R.; Hermelin, Danny (2009), "On problems without polynomial kernels", Journal of Computer and System Sciences , 75 (8): 423–434, doi: 10.1016/j.jcss.2009.04.001 .
Buss, Jonathan F.; Goldsmith, Judy (1993), "Nondeterminism within $P^{*}$ ", SIAM Journal on Computing , 22 (3): 560–572, doi:10.1137/0222038, S2CID 43081484 .
Chen, Jianer; Kanj, Iyad A.; Jia, Weijia (2001), "Vertex cover: Further observations and further improvements", Journal of Algorithms, 41 (2): 280–301, doi:10.1006/jagm.2001.1186, S2CID 13557005 .
Dell, Holger; van Melkebeek, Dieter (2010), "Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses" (PDF), Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010) (PDF), pp. 251–260, doi:10.1145/1806689.1806725, S2CID 1117711 .
Downey, R. G.; Fellows, M. R. (1999), Parameterized Complexity, Monographs in Computer Science, Springer, doi:10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, MR 1656112, S2CID 15271852 .
Flum, Jörg; Grohe, Martin (2006), Parameterized Complexity Theory, Springer, ISBN 978-3-540-29952-3 , retrieved 2010-03-05.
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and kernels", Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503–510.
Jansen, Bart M. P.; Bodlaender, Hans L. (2013), "Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter", Theory Comput. Syst., 53 (2): 263–299, arXiv: 1012.4701 , doi: 10.1007/s00224-012-9393-4 ,
Lampis, Michael (2011), "A kernel of order 2k − c log k for vertex cover", Information Processing Letters , 111 (23–24): 1089–1091, doi:10.1016/j.ipl.2011.09.003 .
Thomassé, Stéphan (2010), "A 4k² kernel for feedback vertex set", ACM Transactions on Algorithms, 6 (2): 1–8, doi:10.1145/1721837.1721848, S2CID 7510317 .
Niedermeier, Rolf (2006), Invitation to Fixed-Parameter Algorithms, Oxford University Press, CiteSeerX 10.1.1.2.9618 , ISBN 0-19-856607-7, archived from the original on 2008-09-24, retrieved 2017-06-01.