Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874677 | Journal of Computer and System Sciences | 2018 | 13 Pages |
Abstract
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(k4)-vertex kernel for the problem, significantly improving the O(k53)-vertex kernel of Fomin et al. (2013) [11]. 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(mn+n2) time, where n and m denote respectively the numbers of vertices and edges of the input graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, Jianxin Wang,