# Optimal prune of a mutually-exclusive 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?

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