Lower bounds on kernelization
From MaRDI portal
Publication:456702
DOI10.1016/j.disopt.2010.10.001zbMath1248.90078OpenAlexW1964699377MaRDI QIDQ456702
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
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (16)
A Retrospective on (Meta) Kernelization ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Studies in Computational Aspects of Voting ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Meta-kernelization with structural parameters ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Bidimensionality and Kernels ⋮ On some FPT problems without polynomial Turing compressions ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Betweenness parameterized above tight lower bound
- Crown reductions for the minimum weighted vertex cover problem
- Parametrized complexity theory.
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Lower Bounds for Kernelizations and Other Preprocessing Procedures
- Polynomial-time data reduction for dominating set
- All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
- Preprocessing of Min Ones Problems: A Dichotomy
- A Cubic Kernel for Feedback Vertex Set
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- A Linear Vertex Kernel for Maximum Internal Spanning Tree
- A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
- Even Faster Algorithm for Set Splitting!
- Nondeterminism within $P^ * $
- Color-coding
- Fixed-Parameter Tractability and Completeness I: Basic Results
- (Meta) Kernelization
- On Independent Circuits Contained in a Graph
- A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Lower bounds on kernelization
