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~$\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).
BibTeX - Entry
@InProceedings{kratsch:LIPIcs:2009:1851,
author = {Stefan Kratsch},
title = {{Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {601--612},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-09-5},
ISSN = {1868-8969},
year = {2009},
volume = {3},
editor = {Susanne Albers and Jean-Yves Marion},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1851},
URN = {urn:nbn:de:0030-drops-18511},
doi = {10.4230/LIPIcs.STACS.2009.1851},
annote = {Keywords: Parameterized complexity, Kernelization, Approximation algorithms}
}
|
Keywords: |
|
Parameterized complexity, Kernelization, Approximation algorithms |
|
Collection: |
|
26th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
19.02.2009 |
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)