Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
From MaRDI portal
Publication:5099101
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
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)
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)