Kernelization

A kernelization is a polynomial-time algorithm mapping a parameterized decision problem instance $(I,k)$ to an equivalent instance $(I^{\prime },k^{\prime })$ of the same problem, with both encoded length $|I^{\prime }|$ and parameter $k^{\prime }$ bounded by a computable function of $k$. Equivalent means that both instances have the same yes/no answer. The bound need not be a polynomial in $k$; a polynomial kernel is the stronger requirement that it is. For a decidable problem, exhaustively solving the bounded output leaves only a computable dependence on $k$, so kernelization yields fixed-parameter tractability.