The maximal f-dependent set problem for planar graphs is in NC

The maximal f-dependent set (Max-f-DS) problem is the following problem: Given a graph G=(V, E) and a nonnegative integer-valued function f defined on V, find a maximal subset U of V such that no vertex u∈U has degree>f(u) in the subgraph induced by U. Whether the problem is in NC (or RNC) or not is an open question. Concerning this question, only a rather trivial result due to Diks, Garrido, and Lingas is known up to now, which says that the problem can be solved in NC if the maximum value of f is poly-logarithmic in the input size [Proceedings of the 2nd International Symposium on Algorithms, LNCS 557 (1991) 385–395]. In this paper, we show a nontrivial interesting result that the Max-f-DS problem for planar graphs can be solved in O(log5n) time with O(n) processors on a CRCW PRAM, where n is the input size.