Proper Interval Vertex Deletion

Deleting a minimum number of vertices from a graph to obtain a proper interval graph is an NP-complete problem. At WG 2010 van Bevern et al. gave an O((14k + 14) k + 1 kn 6) time algorithm by combining iterative compression, branching, and a greedy algorithm. We show that there exists a simple greedy O(n + m) time algorithm that solves the Proper Interval Vertex Deletion problem on \(\{claw,net,\allowbreak tent,\allowbreak C_4,C_5,C_6\}\)-free graphs. Combining this with branching on the forbidden structures \(claw,net,tent,\allowbreak C_4,C_5,\) and C 6 enables us to get an O(kn 6 6 k ) time algorithm for Proper Interval Vertex Deletion, where k is the number of deleted vertices.