## Parameterized complexity of vertex deletion into perfect graph classes

*Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch and Yngve Villanger*

*Theoretical Computer Science*, vol. 511, pp. 172-180, 2013.

[__DOI__][__Preprint__]

A preliminary version of this paper appeared in the proceedings of
FCT 2011, the 18th International Symposium on Fundamentals of Computation Theory (held on August 22-25, 2011 in Oslo, Norway), *Lecture Notes in Computer Science*, vol. 6914, pp. 240-251, 2011.

[__DOI__]

This paper has also been presented at WorKer 2011, the 3rd Workshop on Kernelization (held on September 2-4, 2011 in Vienna, Austria).

[__Slides__]

### Abstract:

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.