Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

DOI10.1137/20M1335285OpenAlexW2944509552MaRDI QIDQ5099101FDOQ5099101

Authors: Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse 

Publication date: 31 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

Recommendations

• Elimination distances, blocking sets, and kernels for Vertex Cover
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• 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

zbMATH Keywords

structural parametersvertex coverkernelizationblocking setselimination distance

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Properties of vertex packing and independence system polyhedra
• Representative sets and irrelevant vertices: new tools for kernelization
• Parameterized algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Vertex packings: Structural properties and algorithms
• Kernelization Lower Bounds by Cross-Composition
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• NP is as easy as detecting unique solutions
• Kernel bounds for disjoint cycles and disjoint paths
• Graph isomorphism parameterized by elimination distance to bounded degree
• Faster parameterized algorithms using linear programming
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Smaller parameters for vertex cover kernelization
• Some observations on the probabilistic algorithms and NP-hard problems
• Vertex cover structural parameterization revisited
• Kernelization. Theory of parameterized preprocessing
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Tractability of König edge deletion problems
• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.

Cited In (3)

• Elimination distances, blocking sets, and kernels for Vertex Cover
• Elimination distance to bounded degree on planar graphs preprint
• Parameterized complexity of computing maximum minimal blocking and hitting sets

This page was built for publication: Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

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