Smaller Parameters for Vertex Cover Kernelization

DOI10.4230/LIPIcs.IPEC.2017.20zbMath1443.68072arXiv1711.04604OpenAlexW2963326511MaRDI QIDQ5111879

Stefan Kratsch, Eva-Maria C. Hols

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1711.04604

zbMATH Keywords

vertex coverkernelizationstructural parameterization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (9)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ On the approximate compressibility of connected vertex cover ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ FPT algorithms for generalized feedback vertex set problems

Cites Work

• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• On problems without polynomial kernels
• On the number of vertices belonging to all maximum stable sets of a graph
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• On the hardness of losing width
• Crown reductions for the minimum weighted vertex cover problem
• Vertex Cover Structural Parameterization Revisited
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Vertex packings: Structural properties and algorithms
• Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Kernelization Lower Bounds by Cross-Composition
• Representative Sets and Irrelevant Vertices
• Unnamed Item

This page was built for publication: Smaller Parameters for Vertex Cover Kernelization