In this note, we give tighter bounds on the complexity of the unique perfect matching problem. We show that the problem for bipartite graphs is in CL and in NLparityL, a subclass of NC2. By a counterexample we show that the solution for the bipartite graphs can not be applied for non-bipartite graphs.
We also consider the (unary) weighted version of the problem. We show that the unique minimum-weight perfect matching problem for bipartite graphs is in LCL and in NLparityL.
Furthermore, we show that the unique perfect matching problem is
hard for NL, even when restricted to bipartite graphs.
(pdf-version)