Unit interval vertex deletion: Fewer vertices are relevant

Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, Jianxin Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)109-121
Number of pages13
JournalJournal of Computer and System Sciences
Publication statusPublished - 1 Aug 2018


  • (Proper, unit) interval model
  • Forbidden induced subgraph
  • Graph modification problem
  • Kernelization
  • Modulator
  • Unit interval graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Unit interval vertex deletion: Fewer vertices are relevant'. Together they form a unique fingerprint.

Cite this