A kernel of order \(2k-c\log k\) for vertex cover

DOI10.1016/j.ipl.2011.09.003zbMath1260.05165OpenAlexW2016639462MaRDI QIDQ1944208

Michael Lampis

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.09.003

zbMATH Keywords

graph algorithmsvertex coverparameterized complexitykernelization algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Parameterized Power Vertex Cover ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ A polynomial kernel for 3-leaf power deletion ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression

Cites Work

• Unnamed Item
• A kernel of order \(2k - c\) for Vertex Cover
• Almost 2-SAT is fixed-parameter tractable
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Vertex Cover: Further Observations and Further Improvements
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On Multiway Cut Parameterized above Lower Bounds
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Vertex packings: Structural properties and algorithms
• Paths, Trees, and Flowers
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

This page was built for publication: A kernel of order \(2k-c\log k\) for vertex cover