Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Eva-Maria C. Hols, Stefan Kratsch & Astrid Pieterse
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.