Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP

Kratsch, Stefan

doi:10.4230/LIPIcs.STACS.2009.1851

Document

Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP

Author Stefan Kratsch

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1851.pdf

Filesize: 196 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1851
URN: urn:nbn:de:0030-drops-18511

Subject Classification

Keywords

Parameterized complexity
Kernelization
Approximation algorithms

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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).

Cite As Get BibTex

Stefan Kratsch. Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 601-612, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1851

Author Details

Stefan Kratsch

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail