A 2k-kernelization algorithm for vertex cover based on crown decomposition

We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming; moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems.

Authors

• Wenjun Li
• Binhai Zhu

Keywords

• Vertex cover
• Crown decomposition
• Kernelization
• FPT algorithms
• NP-completeness