Using maximal independent sets to solve problems in parallel

AbstractWe show that the problem of finding a maximal vertex-induced (resp., edge-induced) subgraph of maximum degree k is in NC2 for k ⩾ 0 (resp., k ⩾ 1). For these problems, we develop a method which exploits the NC algorithm for the maximal independent set problem. By using the same scheme, the maximal vertex-induced subgraph which satisfies a hereditary graph property π and whose maximum degree is at most Δ can be found in time O(Δλ(π)Tπ(n)(log(n + m))2) using a polynomial number of processors, where λ(π) is the maximum of diameters of minimal graphs violating π and Tπ(n) is the time needed to decide whether a graph with n vertices and m edges satisfies π