非表示:
キーワード:
-
要旨:
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~$\textsc{MIN
F}^+\Pi_1$ and~$\textsc{MAX NP}$, including the well-known
subclass~$\textsc{MAX SNP}$, 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~$\textsc{MAX SNP}$
and~$\textsc{MIN F}^+\Pi_1$ are fixed-parameter tractable, and complements
recent research on problems that do not admit polynomial kernelizations
(Bodlaender et al.\ ICALP 2008).
