Result: Polynomial Kernelizations for MIN F+PI 1 and MAX NP
Title:
Polynomial Kernelizations for MIN F+PI 1 and MAX NP
Authors:
Contributors:
Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Susanne Albers and Jean-Yves Marion
Source:
26th International Symposium on Theoretical Aspects of Computer Science STACS 2009. :601-612
Publisher Information:
HAL CCSD; IBFI Schloss Dagstuhl, 2009.
Publication Year:
2009
Collection:
collection:STACS2009
Subject Terms:
Subject Geographic:
Original Identifier:
ARXIV: 0902.1835
HAL:
HAL:
Document Type:
Conference
conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0902.1835
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00360229v1
Database:
HAL
Further Information
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).