Preprocessing, or data reduction, is a standard technique for simplifying and speeding up
computation. Written by a team of experts in the field, this book introduces a rapidly …

We are pleased to dedicate this survey on kernelization of the V ertex C over problem, to
Professor Juraj Hromkovič on the occasion of his 60th birthday. The V ertex C over problem …

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⊆V of size at most k such that each edge in E has at least …

The Vertex Cover problem plays an essential role in the study of polynomial kernelization in
parameterized complexity, ie, the study of provable and efficient preprocessing for NP-hard …

Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether
there exists a subset S⊆ V (G) of size at most k such that G–S is an interval graph. This …

We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in
a graph, using the framework of kernelization. For a fixed finite set of connected graphs F …

Abstract The Connected Vertex Cover problem asks for a vertex cover in a graph that
induces a connected subgraph. The problem is known to be fixed-parameter tractable (FPT) …

A pseudoforest is a graph whose connected components have at most one cycle. Let X be a
pseudoforest modulator of graph G, ie a vertex subset of G such that GX is a pseudoforest …

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
are polynomial time solvable in the class of chordal graphs. We consider these problems in …

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 {\o} mme [WG 2016] who gave a …