# What is known about Vertex Cover Kernelization?

arXiv: https://arxiv.org/abs/1811.09429 · HTML: https://mlsanity.com/paper/1811.09429/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2018.

## Built on by (most cited first, 1 of 1)

- [Disentangling the Computational Complexity of Network Untangling](https://mlsanity.com/paper/2204.02668/) (2022)

## Abstract (arXiv)

We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovivc on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of parameterized complexity. It enjoys a long history. New and worthy perspectives will always be demonstrated first with concrete results here. This survey discusses several research directions in Vertex Cover kernelization. The Barrier Degree of Vertex Cover kernelization is discussed. We have reduction rules that kernelize vertices of small degree, including in this paper new results that reduce graphs almost to minimum degree five. Can this process go on forever? What is the minimum vertex-degree barrier for polynomial-time kernelization? Assuming the Exponential-Time Hypothesis, there is a minimum degree barrier. The idea of automated kernelization is discussed. We here report the first experimental results of an AI-guided branching algorithm for Vertex Cover whose logic seems amenable for application in finding reduction rules to kernelize small-degree vertices. The survey highlights a central open problem in parameterized complexity. Happy Birthday, Juraj!