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.