1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Steven
    Nov 5, 2022 at 11:33
  • $\begingroup$ It is i) There is no cardinality constraint on the matching $\endgroup$ Nov 8, 2022 at 20:08
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Nov 8, 2022 at 20:50
  • $\begingroup$ 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. $\endgroup$ Nov 10, 2022 at 17:41

1 Answer 1

2
$\begingroup$

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.

Ps, this is called the assignment problem and can be solved using LP, by the Hungarian algorithm (augmenting paths), or the min-cost max flow algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.