| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
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.
Your intuition is correct: see here
https://pdfs.semanticscholar.org/ffe1/b723a0cd0319e5ad326088163acf1eed3d9c.pdf
Thanks!
Doesn't König's theorem: https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)#Statement_of_the_theorem allow for a solution in P? Or am I missing something? What is the difference between vertex cover and this problem?
Dominating set and vertex cover are substantially different problems. If you take a path on 6 vertices then second and fifth vertex form dominating set, but they do not form vertex cover (because middle edge is not covered). You can also take triangle, DS=1 and VC=2 there.
Yeah, sorry. I forgot/misremembered the definition of vertex cover.
Isn't it the same problem as finding the minimum vertex cover of the graph? but on a bipartite graph?
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.