Approximating maximum uniquely restricted matchings in bipartite graphs.

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein (2001) and studied in a number of articles. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs, namely those excluding a C 4 or with maximum degree at most three. In particular, we achieve a ratio of 5 ∕ 9 for subcubic bipartite graphs, improving over a 1 ∕ 2 -approximation algorithm proposed by Mishra (2011). [ABSTRACT FROM AUTHOR]