Unit interval editing is fixed-parameter tractable

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

Given a graph G and integers k1, k2, and k3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k1vertex deletions, k2edge deletions, and k3edge additions. We give an algorithm solving this problem in time 2O(klog⁡k)⋅(n+m), where k:=k1+k2+k3, and n,m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed-parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O(4k⋅(n+m)). Another result is an O(6k⋅(n+m))-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O(6k⋅n6).
Original languageEnglish
Pages (from-to)109-126
Number of pages18
JournalInformation and Computation
Volume253
DOIs
Publication statusPublished - 1 Apr 2017

Keywords

  • (Proper, Helly) arc model
  • (Proper, unit) interval model
  • Certifying algorithm
  • Forbidden induced subgraph
  • Graph modification problem
  • Proper Helly circular-arc graph
  • {Claw, S ,S ‾, C }-free graph 3 3 4

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this