Smaller Parameters for Vertex Cover Kernelization

Eva-Maria C. Hols & Stefan Kratsch
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a kernel with O(|X|^{12}) vertices when X is a vertex set such that each connected component of G-X contains at most one cycle, i.e., X is a modulator to a pseudoforest. We strongly generalize this result by using modulators to d-quasi-forests, i.e., graphs where each...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.