Finding minimal 'nice' set of an undirected graph

Revision en1, by 4n1rudh4, 2021-08-31 16:40:37

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.

How can we find a nice set with a minimum size of 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

Tags #bipartite, #greedy, #bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English 4n1rudh4 2021-08-31 18:32:51 147
en2 English 4n1rudh4 2021-08-31 16:41:21 3 Tiny change: 'imum size of an undire' -> 'imum size for an undire'
en1 English 4n1rudh4 2021-08-31 16:40:37 805 Initial revision (published)