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

5 Citations (Scopus)

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

Keywords

  • (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

Cite this