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(n1/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. © 2011 Elsevier B.V.