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
I think I'm being dumb, but for such a set of minimal size, can't you just take 1 node?
What you might actually be asking for is the "maximum independent set". [Here is the wikipedia on this](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)).
If I am not wrong, this is the min vertex cover problem.
correct me if I am wrong but this article explains min vertex problem but the example given is not as per my specifications.
check the last example both 4 and 2 are in the vertex cover. But I am asking when no 2 adjacent vertices are in cover. So ideal answer should be {4,0}
That's minimum independent dominating set.