Lower bounds for kernelizations and other preprocessing procedures

DOI10.1007/S00224-010-9270-YMaRDI QIDQ538466zbMATH OpenOpenAlexFDO

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

Publication date 25 May 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-010-9270-y

zbMATH Keywords

kernelizationlower boundparameterized complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for kernelizations and other preprocessing procedures
• Lower bounds on kernelization
• Kernelization -- preprocessing with a guarantee
• Lower bounds for kernelization
• A hierarchy of polynomial kernels

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• On computing Boolean connectives of characteristic functions
• On Problems without Polynomial Kernels (Extended Abstract)
• SAT-Problems and Reductions with Respect to the Number of Variables
• Some consequences of non-uniform conditions on uniform classes
• 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
• The strong perfect graph theorem
• Which problems have strongly exponential complexity?

Cited in

(26)

• Diminishable parameterized problems and strict polynomial kernelization
• Preprocessing of intractable problems
• Parameterized random complexity
• On some FPT problems without polynomial Turing compressions
• A hierarchy of polynomial kernels
• Kernels for packing and covering problems
• Kernel bounds for path and cycle problems
• A basic parameterized complexity primer
• Kernelization -- preprocessing with a guarantee
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• New limits to classical and quantum instance compression
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Lower bounds for separable approximations of the Hilbert kernel
• Lower bounds for kernelizations and other preprocessing procedures
• Preprocessing of min ones problems: a dichotomy
• Kernel bounds for path and cycle problems
• Lower bounds on kernelization
• Kernelization Lower Bounds by Cross-Composition
• Data-compression for parametrized counting problems on sparse graphs
• Diminishable parameterized problems and strict polynomial kernelization
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• STACS 2005
• Kernelization of packing problems
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• A survey of parameterized algorithms and the complexity of edge modification
• Kernel bounds for disjoint cycles and disjoint paths

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