Lower bounds on kernelization
From MaRDI portal
Publication:456702
DOI10.1016/J.DISOPT.2010.10.001zbMATH Open1248.90078OpenAlexW1964699377MaRDI QIDQ456702FDOQ456702
Authors: Neeldhara Misra, Venkatesh Raman, Saket Saurabh 
Publication date: 16 October 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2010.10.001
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
Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- On problems without polynomial kernels
- Betweenness parameterized above tight lower bound
- Parametrized complexity theory.
- A \(4k^2\) kernel for feedback vertex set
- Incompressibility through Colors and IDs
- Even faster algorithm for set splitting!
- Color-coding
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- (Meta) Kernelization
- On Independent Circuits Contained in a Graph
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Graph-Theoretic Concepts in Computer Science
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Nondeterminism within $P^ * $
- Some consequences of non-uniform conditions on uniform classes
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover: Further observations and further improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- A generalization of Nemhauser and Trotter's local optimization theorem
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Lower bounds for kernelizations and other preprocessing procedures
- Preprocessing of min ones problems: a dichotomy
- A linear vertex kernel for Maximum Internal Spanning Tree
- Title not available (Why is that?)
- A probabilistic approach to problems parameterized above or below tight bounds
- Title not available (Why is that?)
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- Title not available (Why is that?)
- All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
- A Cubic Kernel for Feedback Vertex Set
Cited In (39)
- Studies in Computational Aspects of Voting
- Lower bounds for kernelizations and other preprocessing procedures
- Lower bounds for kernelizations and other preprocessing procedures
- A Retrospective on (Meta) Kernelization
- Kernelization Lower Bounds by Cross-Composition
- Lower bounds for separable approximations of the Hilbert kernel
- Smaller kernels for several FPT problems based on simple observations
- What's next? Future directions in parameterized complexity
- An improved kernel for max-bisection above tight lower bound
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized complexity of machine scheduling: 15 open problems
- Streaming kernelization
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Title not available (Why is that?)
- Kernelization -- preprocessing with a guarantee
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Recent developments in kernelization: a survey
- Towards optimal kernel for edge-disjoint triangle packing
- What Is Known About Vertex Cover Kernelization?
- STACS 2005
- Diminishable parameterized problems and strict polynomial kernelization
- Meta-kernelization with structural parameters
- Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
- Diminishable parameterized problems and strict polynomial kernelization
- Kernelization lower bounds for finding constant-size subgraphs
- Computing kernels in parallel: lower and upper bounds
- Algorithmic Learning Theory
- Kernels: Annotated, Proper and Induced
- Kernelization of packing problems
- Parameterized complexity and kernel bounds for hard planning problems
- Lower bounds for kernelization
- On some FPT problems without polynomial Turing compressions
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Lossy kernelization
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Bidimensionality and kernels
- Confluence in data reduction: bridging graph transformation and kernelization
- A hierarchy of polynomial kernels
- Turing kernelization for finding long paths and cycles in restricted graph classes
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)
