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 inducedby F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in N C (or even in RNC) and is not believed to be parallelizable in general. In this paper we present N C algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in O(log³ n) time with O(n) processors 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 polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in N C. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in O (√n log³ n) time with O(n²) processors on an EREW PRAM.