Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

DOI10.1137/20M1335285MaRDI QIDQ5099101zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

structural parametersvertex coverkernelizationblocking setselimination distance

Mathematics Subject Classification ID

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

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

Cites work

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

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)