A Generalization of Maximal Independent Sets

We generalize the concept of maximal independent set in the following way. For a nonnegative integer k we dene a k-insulated set of a graph G as a subset S of its vertices such that each vertex in S is adjacent to at most k other vertices in S and each vertex not in S is adjacent to at least k +1 vertices in S. We show that it is NP-hard to approximate a maximum k-insulated set within a polynomial factor and describe a polynomial algorithm which approximates a maximum k-insulated set in an n-vertex graph to within the factor of cnk=log 2 n, for a constant c > 0. We also give an O(kn 2 ) algorithm which nds an arbitrary k-insulated set. 1 Introduction For a nonnegative integer k, dene a k-insulated set of a graph G(V; E) as a set S V of vertices such that each vertex in S is adjacent to at most k other vertices in S and each vertex not in S is adjacent to at least k + 1 vertices in S. (If S = V the second condition holds trivially.) The notion of a k-insulated set gener..