Interval Deletion is Fixed-Parameter Tractable

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 10 k · n O (1) for this problem, thereby showing its fixed-parameter tractability.

Authors

• Yixin Cao 0001
• Dániel Marx

Keywords

No keywords are indexed for this paper.