In this note, we give tighter bounds on the complexity of the bipartite unique perfect matching problem, bipartite-UPM. We
show that the problem is in C
=
L and in NL
⊕ L, both subclasses of NC
2.
We also consider the (unary) weighted version of the problem. We show that testing uniqueness of the minimum-weight perfect
matching problem for bipartite graphs is in
LC=L{\rm \bf L}^{{\rm \bf C_=L}} and in
NL
⊕ L.
Furthermore, we show that bipartite-UPM is hard for NL.