Silence_for_Melody's blog

By Silence_for_Melody, history, 10 days ago, In English,

Hi, I would like to know if there is some algorithm to solve the following problem, or maybe it is NP.

Given a bipartite graph of at most 200 nodes in each side, I need to color the minimum number of nodes so each node is colored or has a colored neighbor. The colored nodes could be in any side.

Thanks for your answers.

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

»
10 days ago, # |
  Vote: I like it +16 Vote: I do not like it
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it the same problem as finding the minimum vertex cover of the graph? but on a bipartite graph?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Answering question from title: for every testcase our search space is compact (because it is fine it's), so answer is yes, there is an optimal solution for every testcase.

And for this post to not be completely useless, if I'm not mistaken this problem is NP-complete. I will show a sketch why it is at least as hard as SET COVER. If we consider such problem as you stated but so that only vertices from one side need to be covered then it is exactly set cover. Coming back to original problem we can create one additional vertex on that side that needs to be covered and connect it to all vertices from second side. Maybe up to details, optimal solution takes that additional vertex and optimal set cover from second side.