[Help] A problem about Steiner tree with bipartite graph

Revision en6, by darkkcyan, 2022-04-06 11:53:13

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, whose terminals are nodes on the left side. It is guaranteed that the answer exists.

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.

Sample 1
Sample 2

Also some interseting examples that my friend has drawn:

Friend's graph 1
Friend's graph 2

I have done some Googling, but it's no good. I have found a Wikipedia article called 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 :(.

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)