Finding minimal 'nice' set of an undirected graph

Правка en3, от 4n1rudh4, 2021-08-31 18:32:51

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

Теги #bipartite, #greedy, #bfs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский 4n1rudh4 2021-08-31 18:32:51 147
en2 Английский 4n1rudh4 2021-08-31 16:41:21 3 Tiny change: 'imum size of an undire' -> 'imum size for an undire'
en1 Английский 4n1rudh4 2021-08-31 16:40:37 805 Initial revision (published)