= Kernelization
{wiki}
A <kernelization> is a <polynomial-time algorithm> mapping a parameterized <decision problem> instance $(I,k)$ to an equivalent instance $(I',k')$ of the same problem, with both encoded length $|I'|$ and parameter $k'$ 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>.
Back to article page
