Parallel algorithms for reducible flow graphs

We present parallel NC algorithms for recognizing a reducible now graph (rfg) and for finding dominators, minimum feedback vertex sets, and a depth first search tree in an rfg. On an n-node rfg, all of these algorithms run in polylog(n) time using M(n) processors, where M(n) is the number of processors needed to multiply two n X n matrices in polylog time. We show that finding a minimum feedback vertex set in vertex-weighted rfg's or finding a minimum feedback are set in are-weighted rfg's is P-complete. For are or vertex weights in unary, we present RNC algorithms for these problems and show that the problems are in NC if and only if the problem of finding a minimum cut in a now network is in NC. (C) 1997 Academic Press.