Polynomial Kernelizations for MINF+Pi1 and MAX NP

In parameterized complexity the notion of kernelization allows a systematic study of preprocessing. A kernelization is a polynomial-time transformation that will map an instance~$(x,k)$ to an equivalent instance~$(x',k')$ with~$|x'|$ and~$k'$ bounded by a function~$h(k)$. A kernelization is polynomial if~$h$ is a polynomial.

It has been noted that there seems to be a strong relation between polynomial kernelization and constant factor approximation.

We prove that (naturally parameterized) decision versions of problems from $MIN F^+\Pi_1$ and MAX NP (including MAX SNP) admit polynomial kernelizations. All problems from those classes can be approximated to within a constant factor of the optimum value.