Optimal prune of a mutually-exclusive bipartite graph

Question

I start with a complete edge-weighted unbalanced bipartite graph.

For a known, fixed $n$ on the order of 1000:

$$0 \lt n, n \in I$$

Left and right cardinalities might not be equal; for sides $U$ and $V$:

$$0 < |U| \le |V| = n$$

All edge weights are known, fixed, integral and non-negative.

I need to prune this graph such that

• for every $U$ node, there remains exactly one edge ($U$ becomes 1-regular);
• for every $V$ node, there remains at most one edge;
• it will become disconnected and acyclic;
• the edges are chosen such that the total remaining weight is minimised.

I've had limited success in writing a solution better than a brute-force traversal of all edge permutations. The best attempt - which still scales poorly - is roughly

1. construct an ordered sequence of $U$ nodes
2. let depth $d := 0$, to index into the $U$ nodes
3. at each $d$, let $i$ index into the set of possible edge nodes at $d$
4. If $i$ has not exhausted the possible edges at $d$,
   1. select one of the possible edges $e_{d,i}$ for $U_d$;
   2. calculate the next set of all possible edge choices for $U_{d+1}$ excluding $e_{d,i}$ to pass to state $d+1$;
   3. $d := d + 1$ - but only if the short-circuiting predicate is not true
5. if $i$ has encountered the end of possible edges at $d$, then $d := d - 1$
6. store the lowest-cost option for all depths up to $d$
7. iterate 3-6 until $d = 0$.

The short-circuiting predicate terminates a tree if its accumulated cost from $d=0$ to the current depth is equal to or greater than the lowest cost ever seen to the bottom depth.

To give a sense of how poorly this scales,

n=2 t=7.120e-05
n=3 t=6.440e-05
n=4 t=6.450e-05
n=5 t=6.540e-05
n=6 t=8.680e-05
n=7 t=6.550e-05
n=8 t=8.890e-05
n=9 t=4.275e-04
n=15 t=5.372e-04
n=20 t=1.674e-03
n=30 t=4.620e-02
n=35 t=1.858e-01

Is there an established algorithm that can do better?

Answer 1

Your problem is known as the assignment problem.