Let a 'nice' set S of a graph be a set of vertices such that if v is in S then all neighbors of v in G are not in S. It should also cover all the vertices. That is there should not be any vertex that is neither part of the set S nor neighbor of some element in S.

How can we find a nice set with a minimum size for an undirected graph?

The original problem was about finding such 'nice' set for a tree which could be solved with a greedy approach (choosing all vertices which are parents of leaf nodes and removing the last 3 levels). I am wondering how to calculate such a set for an undirected graph?

Following strategies will not work: 1. Choosing vertex with maximum connectivity and adding it to set S and removing it and all neighbors of v 2. Generating BFS tree and choosing alternate levels 3. Generating BFS tree from maximum degree vertex/ choosing levels with minimum vertices