What Is Known About Vertex Cover Kernelization?
From MaRDI portal
Publication:6163635
Abstract: We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkoviv{c} on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of parameterized complexity. It enjoys a long history. New and worthy perspectives will always be demonstrated first with concrete results here. This survey discusses several research directions in Vertex Cover kernelization. The Barrier Degree of Vertex Cover kernelization is discussed. We have reduction rules that kernelize vertices of small degree, including in this paper new results that reduce graphs almost to minimum degree five. Can this process go on forever? What is the minimum vertex-degree barrier for polynomial-time kernelization? Assuming the Exponential-Time Hypothesis, there is a minimum degree barrier. The idea of automated kernelization is discussed. We here report the first experimental results of an AI-guided branching algorithm for Vertex Cover whose logic seems amenable for application in finding reduction rules to kernelize small-degree vertices. The survey highlights a central open problem in parameterized complexity. Happy Birthday, Juraj!
Recommendations
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
Cites work
- A kernel of order \(2k - c\) for Vertex Cover
- A kernel of order 2k-c k for vertex cover
- Advice classes of parametrized tractability
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An improved fixed-parameter algorithm for vertex cover
- Clique-detection models in computational biochemistry and genomics
- Efficient Classification for Metric Data
- Fundamentals of parameterized complexity
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Heuristic algorithms in computational molecular biology
- 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 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 2080999 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- Improved upper bounds for vertex cover
- Kernelization -- preprocessing with a guarantee
- Kernelization Lower Bounds by Cross-Composition
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Lower bounds based on the exponential time hypothesis
- Lower bounds on kernelization
- LP can be a cure for parameterized problems
- Nondeterminism within $P^ * $
- On problems without polynomial kernels
- On Problems without Polynomial Kernels (Extended Abstract)
- On the complexity of k-SAT
- Optimal Protein Structure Alignment Using Maximum Cliques
- Parameterized algorithm for eternal vertex cover
- Parameterized algorithms
- Parameterized and Exact Computation
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity: New developments and research frontiers
- Properties of vertex packing and independence system polyhedra
- Reducibility among combinatorial problems
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Some consequences of non-uniform conditions on uniform classes
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
- Vertex cover: Further observations and further improvements
- Which problems have strongly exponential complexity?
Cited in
(12)- Reflections on kernelizing and computing unrooted agreement forests
- Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Collaborating with Hans: Some Remaining Wonderments
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Disentangling the computational complexity of network untangling
- On the computational complexity of the strong geodetic recognition problem
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Approximate Turing kernelization for problems parameterized by treewidth
- PACE solver description: GraPA-Java
- There and back again: on applying data reduction rules by undoing others
- Quadratic kernel for cliques or trees vertex deletion
This page was built for publication: What Is Known About Vertex Cover Kernelization?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163635)
