[Help] A problem about Steiner tree with bipartite graph
Difference between en3 and en4, changed 888 character(s)
Hello everyone! There is a problem in an Olympiad from my country 5 years ago, but I could not solve it, nor some of my friends. So I wanted to ask for help with this problem. The problem is as follows:↵

Given a bipartite graph with $n$ nodes on the left side and $m$ nodes on the right side. There is also a weight matrix $C$, $C_{i,j}$ is the weight of the edge connecting the $i$-th node on the left side to the $j$-th node on the right side. The problem ask to find a sub-tree of the graph with minimum total edge weight and it connects every nodes on the left side. In other word, we need to find a minimum [Steiner tree][Steiner-tree], whose terminals are nodes on the left side.↵

Constraints: $n, m \le 1000$. $-1 \le C_{i, j} \le 10000$. $C_{i, j} = -1$ means there is no edge connecting the $i$-th node on the left side and $j$-th node on the right side (or it can be considered $+\infty$).↵

Here is the samples from the problem statement.↵

<spoiler summary="Sample 1">↵

Input (the first line contains $n$ and $m$)↵

```↵
4 3↵
 0 -1  5↵
 0  4  4↵
-1  0 -1↵
 1  2  0↵
```↵

Optimal answer: the cost will be $3$. Besides using all edges with $0$ cost, we use the edges $(4,1)$ (
cost =weights $1$) and $(4,2)$ (cost =weights $2$).↵

</spoiler>↵

<spoiler summary="Sample 2">↵
Input (the first line contains $n$ and $m$)↵

```↵
4 4↵
 0 -1  5  3↵
-1  4  5 -1↵
-1  0 -1  0↵
 6  6  0 -1↵
```↵
</spoiler>↵

Also some _interseting_ examples that my friend has drawn:↵

<spoiler summary="Friend's graph 1">↵

</spoiler>↵


[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem

Besides edges with weight $0$, we can use the edges $(1, 4)$ (weights $3$), $(2, 2)$ (weights $4$), and $(1, 3)$ (weights $5$).↵
</spoiler>↵

Also some _interseting_ examples that my friend has drawn:↵

<spoiler summary="Friend's graph 1">↵
<img src="/predownloaded/64/ec/64ecaf71c721b9a3f774d4314fec40fe8e686c32.png" />↵

This graph shows that plain Kruskal/Prim does not work.↵
</spoiler>↵

<spoiler summary="Friend's graph 2">↵

<img src="/predownloaded/00/ad/00ad90233bd37f966509859c93253b08f303b2b8.png" />↵

</spoiler>↵

I have done some Googling, but it's no good. I have found a Wikipedia article called [Quasi bipartitie graph][Quasi-bipartitie-graph] and there were only approximating solutions. But I'm not sure if this article has anything to do with this problem.↵

Please help me find a solution to this problem, or maybe help me prove this is an NP problem, because I'm really depressed :(.↵

[Steiner-tree]: https://en.wikipedia.org/wiki/Steiner_tree_problem↵
[Quasi-bipartitie-graph]: https://en.wikipedia.org/wiki/Quasi-bipartite_graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English darkkcyan 2022-04-06 12:51:08 2 Update year.
en6 English darkkcyan 2022-04-06 11:53:13 129 Add explanation for the additional examples.
en5 English darkkcyan 2022-04-06 11:20:06 41
en4 English darkkcyan 2022-04-06 11:04:15 888 (published)
en3 English darkkcyan 2022-04-06 10:53:43 327 Add sample 2
en2 English darkkcyan 2022-04-06 10:50:05 294 Add sample 1
en1 English darkkcyan 2022-04-06 10:45:43 1033 Initial revision (saved to drafts)