Smaller parameters for vertex cover kernelization

DOI10.4230/LIPICS.IPEC.2017.20zbMATH Open1443.68072arXiv1711.04604OpenAlexW2963326511MaRDI QIDQ5111879FDOQ5111879

Authors: Eva-Maria C. Hols, Stefan Kratsch 

Publication date: 27 May 2020

Abstract: We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Str{o}mme [WG 2016] who gave a kernel with $mathcalO(|X{|}^{12})$ vertices when $X$ is a vertex set such that each connected component of $G-X$ contains at most one cycle, i.e., $X$ is a modulator to a pseudoforest. We strongly generalize this result by using modulators to $d$-quasi-forests, i.e., graphs where each connected component has a feedback vertex set of size at most $d$, and obtain kernels with $mathcalO(|X{|}^{3d+9})$ vertices. Our result relies on proving that minimal blocking sets in a $d$-quasi-forest have size at most $d+2$. This bound is tight and there is a related lower bound of $mathcalO(|X{|}^{d+2-epsilon})$ on the bit size of kernels. In fact, we also get bounds for minimal blocking sets of more general graph classes: For $d$-quasi-bipartite graphs, where each connected component can be made bipartite by deleting at most $d$ vertices, we get the same tight bound of $d+2$ vertices. For graphs whose connected components each have a vertex cover of cost at most $d$ more than the best fractional vertex cover, which we call $d$-quasi-integral, we show that minimal blocking sets have size at most $2d+2$, which is also tight. Combined with existing randomized polynomial kernelizations this leads to randomized polynomial kernelizations for modulators to $d$-quasi-bipartite and $d$-quasi-integral graphs. There are lower bounds of $mathcalO(|X{|}^{d+2-epsilon})$ and $mathcalO(|X{|}^{2d+2-epsilon})$ for the bit size of such kernels.

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

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 structural parameterization revisited
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

zbMATH Keywords

vertex coverkernelizationstructural parameterization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Kernelization for feedback vertex set via elimination distance to a forest
• 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
• Optimal data reduction for graph coloring using low-degree polynomials
• On the approximate compressibility of connected vertex cover
• Polynomial kernels for vertex cover parameterized by small degree modulators
• FPT algorithms for generalized feedback vertex set problems
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Fixed parameterized algorithms for generalized feedback vertex set problems
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

This page was built for publication: Smaller parameters for vertex cover kernelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111879)