Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
From MaRDI portal
Publication:372970
DOI10.1007/s00224-012-9393-4zbMath1286.68196OpenAlexW3122973673WikidataQ59567529 ScholiaQ59567529MaRDI QIDQ372970
Hans L. Bodlaender, Bart M. P. Jansen
Publication date: 21 October 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-012-9393-4
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, A Multivariate Approach for Weighted FPT Algorithms, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Vertex Cover Structural Parameterization Revisited, Structural parameterizations with modulator oblivion, A multivariate framework for weighted FPT algorithms, A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion, Towards a polynomial kernel for directed feedback vertex set, Meta-kernelization using well-structured modulators, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, FPT algorithms to compute the elimination distance to bipartite graphs and more, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover, Kernelization for feedback vertex set via elimination distance to a forest, Parameterized complexity of computing maximum minimal blocking and hitting sets, What Is Known About Vertex Cover Kernelization?, Unnamed Item, Polynomial kernels for hitting forbidden minors under structural parameterizations, Unnamed Item, Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations., On the approximate compressibility of connected vertex cover, Unnamed Item, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Unnamed Item, The parameterized complexity of cycle packing: indifference is not an issue, Revisiting connected vertex cover: FPT algorithms and lossy kernels, Polynomial kernels for vertex cover parameterized by small degree modulators, Smaller Parameters for Vertex Cover Kernelization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A kernel of order \(2k - c\) for Vertex Cover
- Infeasibility of instance compression and succinct PCPs for NP
- Vertex cover problem parameterized above and below tight bounds
- The complexity of König subgraph problems and above-guarantee vertex cover
- Improved upper bounds for vertex cover
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Parameterized complexity of vertex colouring
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
- On the Hardness of Losing Width
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Spanning trees with many leaves in cubic graphs
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Paths, Flowers and Vertex Cover
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Two-Layer Planarization Parameterized by Feedback Edge Set
- Isomorphism for Graphs of Bounded Feedback Vertex Set Number
- Graph Layout Problems Parameterized by Vertex Cover
- Incompressibility through Colors and IDs
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- The structure and maximum number of maximum independent sets in trees
- Vertex packings: Structural properties and algorithms
- Nondeterminism within $P^ * $
- On efficient fixed-parameter algorithms for weighted vertex cover
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Kernels for the Vertex Cover Problem on the Preferred Attachment Model
- Graph-Theoretic Concepts in Computer Science
