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 vertic es in this set makes the graph acyclic. This problem is known to be NP -hard on general graphs. An O(n(6)) algorithm for this problem on perm utation graphs is known. In this paper, we give an O(n(4)) algorithm f or this problem on cocomparability graphs. Our result improves the tim e complexity of the algorithm and enlarges the class of graphs on whic h this problem is polynomial time-solvable. (C) 1995 John Wiley and So ns, Inc.