On the feedback vertex set problem in permutation graphs

Brandstat and Kratsch presented an O(n⁶) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O(n.m.&mmacr;) by Brandstadt, where &mmacr; is the number of edges in the complement of G. In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O(nm) for this problem in permutation graphs.