An Algorithm to find a Minimum Feedback Vertex Set of an Interval Graph

In an undirected graph, the feedback vertex set problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic (connected or disconnected). This problem is known to be NP-hard for general graph. In this paper, we proposed two algorithms for finding the minimum feedback vertex set on interval graphs. The first algorithm is for unweighted case and takes O(n + m) time while the second one is for weighted case taking O(n p logC) time where n is the number of vertices, m is the number of edges and C is the cost of the longest path of the graph.