Skip to Main content Skip to Navigation
Conference papers

Polynomial Kernelizations for MIN F+PI 1 and MAX NP

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~$\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).
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00360229
Contributor : Publications Loria <>
Submitted on : Tuesday, February 10, 2009 - 4:39:44 PM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 7:19:07 PM

Files

kratsch_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00360229, version 1
  • ARXIV : 0902.1835

Collections

Citation

Stefan Kratsch. Polynomial Kernelizations for MIN F+PI 1 and MAX NP. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.601-612. ⟨inria-00360229⟩

Share

Metrics

Record views

94

Files downloads

291