an nc algorithm for finding a maximal acyclic set in a graph
An acyclic set in an undirected graph G = ( V,E ) is a set A ? V ( G ) such that the induced graph on A is acyclic. A maximal acyclic set (MAS) has the further property that no vertex can be added to it without creating a cycle in the induced graph. We present the first NC algorithm that finds an MAS in any graph, running in time O (log 4 n ) using O (( m 2 + n )/log n ) processors on a EREW PRAM, answering questions raised by Chen and He. Our NC algorithm for finding an MAS in a graph relies on a novel NC algorithm for finding a maximal forest in a hypergraph which may be of independent interest.
nc algorithms maximal acyclic set maximal forest graph algorithms hypergraph algorithms