On the Maximum Uniquely Restricted Matching for Bipartite Graphs

We study the approximability of computing a maximum size uniquely restricted matching in a given bipartite graph. We prove that it is hard to approximate within a factor of O ( n 1 3 − ϵ ) , for any ϵ > 0 , unless NP=ZPP, and it is APX-complete when restricted to bipartite graphs of degree at most 3. We show that it can be approximated within a factor of 2 when restricted to 3-regular bipartite graphs.