Lower Bounds for Kernelizations and Other Preprocessing Procedures

DOI10.1007/978-3-642-03073-4_13zbMath1268.68084OpenAlexW1744692106MaRDI QIDQ3576044

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

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

parameterized complexitykernelizationpreprocessing

Mathematics Subject Classification ID

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

Related Items (6)

A new bound for 3-satisfiable MaxSat and its algorithmic application ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Lower bounds on kernelization ⋮ Confronting intractability via parameters ⋮ A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications ⋮ A New Bound for 3-Satisfiable Maxsat and Its Algorithmic Application

Cites Work

• Unnamed Item
• Which problems have strongly exponential complexity?
• The complexity of first-order and monadic second-order logic revisited
• On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
• On Problems without Polynomial Kernels (Extended Abstract)
• Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
• SAT-Problems and Reductions with Respect to the Number of Variables
• On computing Boolean connectives of characteristic functions
• The NP-completeness column: An ongoing guide

This page was built for publication: Lower Bounds for Kernelizations and Other Preprocessing Procedures