On the Bipartite Unique Perfect Matching Problem

Thanh Minh Hoang, Meena Mahajan, and Thomas Thierauf

Abstract:
Lovász has posed the question of whether the problem of testing if a graph has precisely one perfect matching is in NC. This unique perfect matching question has been answered positively by Kozen, Vazirani, and Vazirani for bipartite graphs.

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)