Unit Interval Vertex Deletion: Fewer Vertices are Relevant
The unit interval vertex deletion problem asks for a set of at most $k$ vertices whose deletion from a graph makes it a unit interval graph. We develop an $O(k^4)$-vertex kernel for the problem, significantly improving the $O(k^{53})$-vertex kernel of Fomin, Saurabh, and Villanger [ESA'12; SIAM J.\ Discrete Math 27(2013)]. We start from a constant-approximation solution and study its interaction with other vertices, which induce a unit interval graph. We partition vertices of this unit interval graph into cliques in a naive way, and pick a small number of representatives from each of them. Our constructive proof for the correctness of our algorithm, using interval models, greatly simplifies the ``destructive'' proofs, based on destroying forbidden structures, for similar problems in literature. Our algorithm can be implemented in $O(m n + n^2)$ time, where $n$ and $m$ denote respectively the numbers of vertices and edges of the input graph.