## 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*((14*k* +14)^{k+1} *kn*^{6}) time. We improve this result by presenting an *O*(6^{k} *kn*^{6}) 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*_{4},*C*_{5},*C*_{6}}-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*_{4},*C*_{5},*C*_{6}}-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.