Pim van 't Hof

Proper interval vertex deletion

Pim van 't Hof and Yngve Villanger

Algorithmica, Algorithmica, vol. 65, no. 4, pp. 845-867, 2013.
[DOI][Preprint]

A preliminary version of this paper appeared in the proceedings of IPEC 2010, the 5th International Symposium on Parameterized and Exact Computation (held on December 13-15, 2010, Chennai, India), Lecture Notes in Computer Science, vol. 6478, pp. 228-238, 2010.
[DOI]

Abstract:

The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (WG 2010) showed that this problem can be solved in O((14k +14)^k+1 kn⁶) time. We improve this result by presenting an O(6^k kn⁶) time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw,net,tent,C₄,C₅,C₆}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw,net,tent,C₄,C₅,C₆}-free graphs in O(n+m) time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.