Vertex cover structural parameterization revisited
From MaRDI portal
Abstract: A pseudoforest is a graph whose connected components have at most one cycle. Let X be a pseudoforest modulator of graph G, i. e. a vertex subset of G such that G-X is a pseudoforest. We show that Vertex Cover admits a polynomial kernel being parameterized by the size of the pseudoforest modulator. In other words, we provide a polynomial time algorithm that for an input graph G and integer k, outputs a graph G' and integer k', such that G' has O(|X|12) vertices and G has a vertex cover of size k if and only if G' has vertex cover of size k'. We complement our findings by proving that there is no polynomial kernel for Vertex Cover parameterized by the size of a modulator to a mock forest (a graph where no cycles share a vertex) unless NP is a subset of coNP/poly. In particular, this also rules out polynomial kernels when parameterized by the size of a modulator to outerplanar and cactus graphs.
Recommendations
- Smaller parameters for vertex cover kernelization
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Structural Parameterizations of Feedback Vertex Set
- A faster parameterized algorithm for pseudoforest deletion
Cites work
- A unified approximation algorithm for node-deletion problems
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- On the hardness of losing width
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
Cited in
(25)- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Graph Layout Problems Parameterized by Vertex Cover
- Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
- Smaller parameters for vertex cover kernelization
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- On the approximate compressibility of connected vertex cover
- An improved FPT algorithm for almost forest deletion problem
- Core influence mechanism on vertex-cover problem through leaf-removal-core breaking
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
- What Is Known About Vertex Cover Kernelization?
- Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
- Vertex cover structural parameterization revisited
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs
- Lower bounds for protrusion replacement by counting equivalence classes
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Vertex Cover Reconfiguration and Beyond
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Difference determines the degree: structural kernelizations of component order connectivity
- Approximating V<scp>ertex</scp> C<scp>over</scp> using Structural Rounding
This page was built for publication: Vertex cover structural parameterization revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3181056)
