Unit Interval Vertex Deletion: Fewer Vertices are Relevant

Yuping Ke, Yixin Cao, Xiating Ouyang +1

The unit interval vertex deletion problem asks for a set of at most $k$ vertices whose deletion from an $n$-vertex graph makes it a unit interval graph. We develop an $O(k^4)$-vert…