Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter

Bart M. P. Jansen, Hans L. Bodlaender

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',…