Given a complete bipartite graph $G=\{A+B,W\}$ with the number of vertices $|A|<|B|$, suppose I am looking for a subset $B'\subset B$ with $|B'|=|A|$ such that the minimum weight perfect matching between the vertices $a_i\in A$ and $b_i\in B'$ has the minimum weight among all such possible $B'$s. The straightforward way to solve it would be to enumerate all possible $B'$ and then solve each case by Hungarian algorithm. Is there any better algorithm to solve it?
Variant of minimum weight perfect matching problem with Hungarian algorithm
algorithmsgraph theorymatching-theory
Best Answer
You can solve this with one call to the Hungarian algorithm on an auxiliary complete bipartite graph. Introduce $|B|-|A|$ new vertices on the $A$ side so that the left and right node sets have the same cardinality $|B|$. For the new nodes, let all the edge weights be an arbitrary constant (say, $0$). The nodes in $B$ that get matched to the original nodes yield your desired $B’$.