Uniquely Restricted Matchings

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 amatrix 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 and of finding a maximum u.r. matching in a given graph, and present algorithms and 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 an arbitrary graph G = (V, E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum u.r. matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs.