USING MAXIMAL INDEPENDENT SETS TO SOLVE PROBLEMS IN PARALLEL

We show that the problem of finding a maximal vertex-induced (reap., e dge-induced) subgraph of maximum degree k is in NC2 for k greater than or equal to 0 (resp., k greater than or equal to 1). Far these proble ms, we develop a method which exploits the NC algorithm for the maxima l independent set problem. By using the same scheme, the maximal verte x-induced subgraph which satisfies a hereditary graph property pi and whose maximum degree is at most Delta can be found in time O(Delta(lam bda(pi))T-pi(n)(log(n + m))(2)) using a polynomial number of processor s, where lambda(pi) is the maximum of diameters of minimal graphs viol ating pi and T-pi(n) is the time needed to decide whether a graph with n vertices and m edges satisfies pi.