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?

  • 2
    $\begingroup$ Sounds very similar to maximum bipartite matching, a well-known problem with efficient algorithms. $\endgroup$ Commented Feb 7, 2022 at 20:11
  • $\begingroup$ A matching is always "disconnected and acyclic" (unless $|U|=|V|=1$). $\endgroup$ Commented Feb 7, 2022 at 20:12
  • $\begingroup$ You can convert between the minimum and maximum versions of the problem by negating the edge weights. $\endgroup$ Commented Feb 7, 2022 at 20:14
  • $\begingroup$ @YuvalFilmus So basically Bipartite min-cost perfect matching as described on page 12 of Cornell's Matchings notes $\endgroup$
    – Reinderien
    Commented Feb 8, 2022 at 23:34
  • $\begingroup$ Bipartite perfect matching is described in many sources. $\endgroup$ Commented Feb 9, 2022 at 5:37

1 Answer 1


Your problem is known as the assignment problem.


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.