Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies

Bart M. P. Jansen, Jari J. H. de Kroon

We consider the $\Pi$-free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties $\Pi$. Given an input graph $G$, this problem asks whether ther…