Feedback vertex set on cocomparability graphs

Given an undirected graph, The feedback vertex set problem is to find a set of vertices of minimum cardinality such that removing the vertices in this set makes the graph acyclic. This problem is known to be NP‐hard on general graphs. An O(n6) algorithm for this problem on permutation graphs is known. in this paper, we give an O(n4) algorithm for this problem on cocomparability graphs. Our result improves the time complexity of the algorithm and enlarges the class of graphs on which this problem is polynomial time‐solvable. Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company