10.4230/LIPICS.STACS.2009.1851
Kratsch, Stefan
Stefan
Kratsch
Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Parameterized complexity
Kernelization
Approximation algorithms
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
2009
2009-02-19
2009-02-19
2009-02-19
en
urn:nbn:de:0030-drops-18511
10.4230/LIPIcs.STACS.2009
978-3-939897-09-5
1868-8969
10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS 2009
26th International Symposium on Theoretical Aspects of Computer Science
2013
3
49
601
612
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
3
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
200808 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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).
LIPIcs, Vol. 3, 26th International Symposium on Theoretical Aspects of Computer Science, pages 601-612