Lower bounds for kernelizations and other preprocessing procedures
DOI10.1007/S00224-010-9270-YzbMATH Open1234.68118OpenAlexW2051784313MaRDI QIDQ538466FDOQ538466
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- The strong perfect graph theorem
- Some consequences of non-uniform conditions on uniform classes
- On computing Boolean connectives of characteristic functions
- The complexity of first-order and monadic second-order logic revisited
- Title not available (Why is that?)
- 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
- The NP-completeness column: An ongoing guide
Cited In (26)
- Kernel bounds for path and cycle problems
- Lower bounds for kernelizations and other preprocessing procedures
- Kernelization Lower Bounds by Cross-Composition
- Lower bounds for separable approximations of the Hilbert kernel
- A basic parameterized complexity primer
- Data-compression for parametrized counting problems on sparse graphs
- Preprocessing of min ones problems: a dichotomy
- Title not available (Why is that?)
- Kernelization -- preprocessing with a guarantee
- Kernel bounds for disjoint cycles and disjoint paths
- A survey of parameterized algorithms and the complexity of edge modification
- Monotonic reductions, representative equivalence, and compilation of intractable problems
- Lower bounds on kernelization
- STACS 2005
- Diminishable parameterized problems and strict polynomial kernelization
- Diminishable parameterized problems and strict polynomial kernelization
- Kernel bounds for path and cycle problems
- New limits to classical and quantum instance compression
- Kernelization of packing problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Preprocessing of intractable problems
- Parameterized random complexity
- On some FPT problems without polynomial Turing compressions
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Kernels for packing and covering problems
- A hierarchy of polynomial kernels
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)
