PARALLEL ALGORITHMS FOR MAXIMAL ACYCLIC SETS

Given a graph G = (V, E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this probl em has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset ti of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In t his paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vert ices, the problem can be solved in O(log(3) n) time with O(n) processo rs on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polyloga rithmic in the number of vertices of G. As a consequence of this resul t, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that , for a constant-degree graph with n vertices, the problem can be solv ed in O(root n log(3) n) time with O(n(2)) processors on an EREW PRAM.