# Maximum weighted matching in Bipartite Graph

I was solving a coding question which boiled down to this problem.
Given a bipartite graph $$G=\{V\cup U,E\}$$. There is a positive value given for every node in $$U$$.
Now we have to find the matching in which the sum of value of every node in $$U$$ which is also in the matching is maximum.
Consider an example, Let valueArray for $$U = [1,2,3]$$ . If in a matching nodes 0 and 1 of array are in matching the value of matching will be valueArray[0]+valueArray[1] = 3.
We have to find this maximum possible value of all possible matching given the graph and valueArray.
Matching nedd not be of maximum cardinality.

• It's unclear what you want to maximize. Let $M$ be the maximum cardinality over all matchings of $G$ (recall that a matching is a set of edges). Are you looking to maximize (i) the sum of the values of the matched nodes in $U$ over all possible matchings of $G$, or (ii) the sum of the values of the matched nodes in $U$ over all possible matchings of $G$ of cardinality $M$? Nov 5, 2022 at 11:33
• It is i) There is no cardinality constraint on the matching Nov 8, 2022 at 20:08
• Then you just want a maximum weight bipartite matching. Use the transformation in Pål GD's answer to get the edge-weighted variant. Then add dummy edges of weight $0$ to ensure that a perfect matching always exists. Finally, use any algorithm for minimum/maximum weight bipartite matching. See again Pål GD's answer. Nov 8, 2022 at 20:50
• Thanks for answer. But I was thinking whether the question has a simpler solution as it was one of the three question asked in exam having 60 mins time to complete the code for all the three. Nov 10, 2022 at 17:41

You can turn the problem into an edge-weighted variant by setting the weight on edge $$vu$$ to be $$\texttt{valueArray}(u)$$ where $$w(vu) = \texttt{valueArray}(u)$$ is the value of $$u \in U$$.
Now a maximum weight matching in this graph is a matching which maximizes the sum of the values of the nodes in $$U$$. Note that you can flip the sign of all values to obtain a minimization problem, and if you add all missing edges with $$w(e) = 0$$. Now you have a minimum-weight perfect matching problem.