**A** matching in **a** graph is **a** set of edges no two of which share **a** common vertex. In this paper, we introduce **a** new, specialized type of matching which we call uniquely restricted (u.r) matchings, originally motivated by the problem of determining **a** lower bound on the rank of **a**matrix having **a** specified zero/non-zero pattern. **A** uniquely restricted matching is defined to be **a** matching M whose saturated vertices induce **a** subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing **a** u.r. matching **a**nd of finding **a** maximum u.r. matching in **a** given graph, **a**nd present **a**lgorithms **a**nd complexity results for certain special classes of graphs. We demonstrate that testing whether **a** given matching M is uniquely restricted can be done in O(|M||E|) time for **a**n **a**rbitrary graph G = (V, E) **a**nd in linear time for cacti, interval graphs, bipartite graphs, split graphs **a**nd threshold graphs. The maximum u.r. matching problem is shown to be NP-complete for bipartite graphs, split graphs, **a**nd hence for chordal graphs **a**nd comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti **a**nd block graphs.

By:* Martin Charles Golumbic, Tirza Hirst, Moshe Lewenstein*

Published in: Algorithmica , volume 31, (no 2), pages 139-54 in 2001

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions **a**bout this service can be mailed to reports@us.ibm.com .