Hello everyone! There is a problem in an Olympiad from my country 7 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.
Also some interseting examples that my friend has drawn:
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 :(.
Auto comment: topic has been updated by darkkcyan (previous revision, new revision, compare).
I think MCMF might work,consider a new graph with $$$cap_{i,j}=1,cost_{i,j}=c_{i,j}$$$,and also connect s to all left nodes,right nodes to t.Since you have to choose n+m-1 edges(it's a tree),you can add an additional edge s'->s,with capacity of n+m-1 and cost of inf.Then it becomes a max flow min cost problem.
Thank you for your response. But the tree that we need to find does not need to have $$$n + m - 1$$$ edges, because we don't need to connect all the nodes on the right sides, but only nodes on the left sides. Please see 2 additional graphs that my friends has drawn. In both of them, there are 5 nodes, but we only need to connect $$$3$$$ edges in total.
Also the flow model don't really guarantee the connectivity condition.
True,my bad.
Apparently, it is an NP-hard problem.
Let's take a Set Cover Problem with $$$U = \lbrace 1,2,\dots,n \rbrace$$$ and $$$S = \lbrace S_1, S_2,\dots,S_m \rbrace$$$. Now we build a bipartite graph with $$$n+1$$$ nodes on left side, and $$$m$$$ nodes on right side. All the weights of existing edges would be equal.
Node $$$0$$$ on the left side is connected to every node on the right side. Node $$$v \gt 0$$$ on the left side is connected to node $$$t$$$ on the right side iff $$$v \in S_t$$$.
So, if we solve a task from the blog on a constructed graph, we will use the minimal number of nodes on the right side, and so we solve a Set Cover Problem.
P.S.: how to use curly brackets in cf tex? backslash doesn't help :(
P.P.S.: now I can use them! thanks!
The braces is like this: $$$\lbrace 1, 2, 3 \rbrace $$$
Thank you so much for your response! It took me a bit to think why must we use the minimal number of nodes while what we need is the minimum number of edges, but the reason is because of the nature of MST. Again, thank you for spending your time!
For some reason you need to use double blackslash in cf