Lower bounds for kernelizations and other preprocessing procedures

DOI10.1007/978-3-642-03073-4_13MaRDI QIDQ3576044zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum, Moritz Müller

Publication date 28 July 2010

Published in Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03073-4_13

zbMATH Keywords

kernelizationparameterized complexitypreprocessing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds for kernelizations and other preprocessing procedures
• Lower bounds on kernelization
• Lower bounds for kernelization
• Diminishable parameterized problems and strict polynomial kernelization
• A hierarchy of polynomial kernels

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• On computing Boolean connectives of characteristic functions
• On Problems without Polynomial Kernels (Extended Abstract)
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• SAT-Problems and Reductions with Respect to the Number of Variables
• Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
• The complexity of first-order and monadic second-order logic revisited
• The NP-completeness column: An ongoing guide
• Which problems have strongly exponential complexity?

Cited in

(12)

• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Lower bounds for separable approximations of the Hilbert kernel
• Preprocessing of min ones problems: a dichotomy
• A new bound for 3-satisfiable MaxSat and its algorithmic application
• Lower bounds on kernelization
• Confronting intractability via parameters
• Kernelization Lower Bounds by Cross-Composition
• Diminishable parameterized problems and strict polynomial kernelization
• Lower bounds for kernelizations and other preprocessing procedures
• STACS 2005
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP

This page was built for publication: Lower bounds for kernelizations and other preprocessing procedures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576044)