Prefer a chat interface with context about you and your work?
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
In the vertex cover problem we are given a graph $G=(V,E)$ and an integer $k$ and have to determine whether there is a set $X\subseteq V$ of size at most $k$ such that each edge in $E$ has at least one endpoint in $X$. The problem can be easily solved …