Lower bounds on kernelization
From MaRDI portal
Recommendations
- Lower bounds for kernelization
- Lower bounds for kernelizations and other preprocessing procedures
- Lower bounds for kernelizations and other preprocessing procedures
- Kernelization: new upper and lower bound techniques
- Kernelization Lower Bounds by Cross-Composition
- A universal lower bound for the kernel estimate
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Fractals for kernelization lower bounds
- Lower bounds for separable approximations of the Hilbert kernel
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
Cites work
- (Meta) Kernelization
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- A 4k^2 kernel for feedback vertex set
- A Cubic Kernel for Feedback Vertex Set
- A generalization of Nemhauser and Trotter's local optimization theorem
- A linear vertex kernel for Maximum Internal Spanning Tree
- A probabilistic approach to problems parameterized above or below tight bounds
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- Betweenness parameterized above tight lower bound
- Color-coding
- Crown reductions for the minimum weighted vertex cover problem
- Even faster algorithm for set splitting!
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 5485524 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2011849 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Lower bounds for kernelizations and other preprocessing procedures
- Nondeterminism within $P^ * $
- On Independent Circuits Contained in a Graph
- On problems without polynomial kernels
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Parametrized complexity theory.
- Polynomial-time data reduction for dominating set
- Preprocessing of min ones problems: a dichotomy
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Some consequences of non-uniform conditions on uniform classes
- Vertex cover: Further observations and further improvements
Cited in
(41)- Diminishable parameterized problems and strict polynomial kernelization
- Kernelization lower bounds for finding constant-size subgraphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized complexity of machine scheduling: 15 open problems
- An improved kernel for max-bisection above tight lower bound
- On some FPT problems without polynomial Turing compressions
- A hierarchy of polynomial kernels
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Towards optimal kernel for edge-disjoint triangle packing
- Kernelization -- preprocessing with a guarantee
- Studies in Computational Aspects of Voting
- What's next? Future directions in parameterized complexity
- Streaming kernelization
- Lower bounds for kernelization
- Bidimensionality and kernels
- Smaller kernels for several FPT problems based on simple observations
- Kernels: Annotated, Proper and Induced
- 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
- Parameterized complexity and kernel bounds for hard planning problems
- Recent developments in kernelization: a survey
- Lossy kernelization
- Kernelization Lower Bounds by Cross-Composition
- Computing kernels in parallel: lower and upper bounds
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- A Retrospective on (Meta) Kernelization
- Diminishable parameterized problems and strict polynomial kernelization
- Lower bounds for kernelizations and other preprocessing procedures
- Algorithmic Learning Theory
- STACS 2005
- Kernelization of packing problems
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Confluence in data reduction: bridging graph transformation and kernelization
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- What Is Known About Vertex Cover Kernelization?
- Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
- Parameterized lower bounds for the weighted vertex cover problem in trees
- Parameterized complexity of feedback vertex set with connectivity constraints
- Meta-kernelization with structural parameters
This page was built for publication: Lower bounds on kernelization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456702)
