Interval Deletion is Fixed-Parameter Tractable
classification
💻 cs.DS
cs.DM
keywords
intervalproblemdeletionfixed-parametergraphtractableverticesalgorithm
read the original abstract
We study the minimum \emph{interval deletion} problem, which asks for the removal of a set of at most $k$ vertices to make a graph of $n$ vertices into an interval graph. We present a parameterized algorithm of runtime $10^k \cdot n^{O(1)}$ for this problem, that is, we show the problem is fixed-parameter tractable.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.