ON FINDING CRITICAL INDEPENDENT AND VERTEX SETS

An independent set I(C) of a undirected graph G is called critical if \I(C)\ - \N(I(C))\ = max{\I\ - \N(I)\ : I is an independent set of G}, where N(I) is the set of all vertices of G adjacent to some vertex of I. It has been proved by Cun-Quan Zhang [SIAM J. Discrete Math., 3 (1990), pp. 431 438] that the problem of finding a critical independent set is polynomially solvable. This paper shows that the problem can be solved in O(\V(G)\1/2\E(G)\) time and its weighted version in O(\V(G)\2\E(G)\1/2) time.