Блог пользователя Silence_for_Melody

Автор Silence_for_Melody, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.