Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

Marin Bougeret, Bart M. P. Jansen, Ignasi Sau

We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can redu…