Feedback vertex set on cocomparability graphs
Satyan R. Coorg, Chandrasekharan Pandu Rangan · Networks · 1995
Abstract 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 ( n 6 ) algorithm for this problem on permutation graphs is known. in this paper, we give an O ( n 4 ) 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.