Polynomial Kernelizations for MIN F+PI 1 and MAX NP

Abstract : The relation of constant-factor approximability to fixed-parameter tractability and kernelization is a long-standing open question. We prove that two large classes of constant-factor approximable problems, namely~$\MINF_1$ and~$\MNP$, including the well-known subclass~$\MSNP$, admit polynomial kernelizations for their natural decision versions. This extends results of Cai and Chen (JCSS 1997), stating that the standard parameterizations of problems in~$\MSNP$ and~$\MINF_1$ are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al.\ ICALP 2008).