Interval deletion is fixed-parameter tractable

Yixin Cao, Dániel Marx

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)


We study the minimum interval deletion problem, which asks for the removal of a set of at most κ vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10κ· nO(1)for this problem-that is, we show that the problem is fixed-parameter tractable.
Original languageEnglish
Article number21
JournalACM Transactions on Architecture and Code Optimization
Issue number3
Publication statusPublished - 1 Jan 2014


  • Algorithms

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Interval deletion is fixed-parameter tractable'. Together they form a unique fingerprint.

Cite this