MINIMUM FEEDBACK VERTEX SETS IN COCOMPARABILITY GRAPHS AND CONVEX BIPARTITE GRAPHS

It is well-known that the feedback vertex set problem is NP-complete f or general graphs and even for bipartite graphs [6]. However, this pro blem can be solved in polynomial time for several special graphs such as interval graphs and permutation graphs. Convex bipartite graphs are subclasses of bipartite graphs, and cocomparability graphs are a supe rclass of permutation graphs and interval graphs. It is interesting to investigate the complexity of the feedback vertex set problem in coco mparability graphs and convex bipartite graphs, We develop polynomial time algorithms for the feedback vertex set problem using dynamic prog ramming techniques by exploring the structural properties of these two types of graphs. The paper is organized as follows. In Section 2, we provide background material. We present an O(\V\(2)\E\)lime algorithm for finding a minimum weight feedback vertex set on a cocomparability graph G = (V, E) in Section 3 and an O(\A\(3) + \A\(2)\E\) time algori thm for the same problem on a convex bipartite graph G = (A, B, E) in Section 4.