Parallelism and the feedback vertex set problem (Q1111395)

The feedback vertex set problem consists of finding in a digraph \(G=(N,E)\) a minimum set of vertices such that each cycle in G includes at least a vertex of such a set. It is shown that this problem is logspace- complete for P when G is cyclically reducible. A parallel algorithm requiring O(k \(log^ 2 n)\) time and \(O(n^ 4)\) processors is presented, where k denotes the cardinality of the minimum feedback vertex set.