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 , 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.