Smaller parameters for vertex cover kernelization

DOI10.4230/LIPICS.IPEC.2017.20MaRDI QIDQ5111879zbMATH OpenOpenAlexFDO

Authors Eva-Maria C. Hols, Stefan Kratsch

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) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

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.

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

Cites work

• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Crown reductions for the minimum weighted vertex cover problem
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Kernelization Lower Bounds by Cross-Composition
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• On problems without polynomial kernels
• On the hardness of losing width
• On the number of vertices belonging to all maximum stable sets of a graph
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Representative sets and irrelevant vertices: new tools for kernelization
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Vertex cover structural parameterization revisited
• Vertex packings: Structural properties and algorithms
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph

Cited in

(14)

• Vertex cover structural parameterization revisited
• Kernelization for feedback vertex set via elimination distance to a forest
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• FPT algorithms for generalized feedback vertex set problems
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• Kernelization for feedback vertex set via elimination distance to a forest
• Optimal data reduction for graph coloring using low-degree polynomials
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Fixed parameterized algorithms for generalized feedback vertex set problems
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• On the approximate compressibility of connected vertex cover
• Elimination distances, blocking sets, and kernels for Vertex Cover

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)