Parameterized complexity of vertex deletion into perfect graph classes

Vertex deletion problems are at the heart of parameterized complexity. For a graph class  F, the  F-Deletion problem takes as input a graph  G and an integer  k. The question is whether it is possible to delete at most  k vertices from  G such that the resulting graph belongs to  F. Whether Perfect Deletion is fixed-parameter tractable, and whether Chordal Deletion admits a polynomial kernel, when parameterized by  k, have been stated as open questions in previous work. We show that Perfect Deletion and Weakly Chordal Deletion are  W[2]-hard when parameterized by  k. In search of positive results, we study a restricted variant of the  F-Deletion problem. In this restricted variant, the deleted vertices must be taken from a specified set  X, and we parameterize by  |X|. We show that for Perfect Deletion and Weakly Chordal Deletion, although this restriction immediately ensures fixed-parameter tractability, it is not enough to yield polynomial kernels, unless NP  ⊆  coNP/poly. On the positive side, for Chordal Deletion, the restriction enables us to obtain a kernel with  O(|X|4) vertices.