Interval deletion is fixed-parameter tractable

Yixin Cao, Dániel Marx

Research output: Journal article publicationJournal articleAcademic researchpeer-review

37 Citations (Scopus)

Abstract

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
Volume11
Issue number3
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Algorithms

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this