Interval deletion is fixed-parameter tractable

Yixin Cao, Dániel Marx

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph on n vertices into an interval graph. We present a parameterized algorithm of runtime 10k. nO(1)for this problem, thereby showing its fixed-parameter tractability.
Original languageEnglish
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages122-141
Number of pages20
ISBN (Print)9781611973389
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: 5 Jan 20147 Jan 2014

Conference

Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR
Period5/01/147/01/14

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this