On the complexity of minimum maximal uniquely restricted matching.

• We prove that Decide-UR Matching problem is NP-complete for chordal bipartite graphs and star-convex bipartite graphs. • We prove that Decide-UR Matching problem is NP-complete for chordal graphs and doubly chordal graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in polynomial time for bipartite distance-hereditary graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in linear time for bipartite permutation graphs, proper interval graphs, and threshold graphs. • We prove that the problem is APX-complete for bounded degree graphs. A subset M ⊆ E of edges of a graph G = (V , E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called a uniquely restricted matching if, G [ V (M) ] , the subgraph of G induced by the set of M -saturated vertices of G contains exactly one perfect matching. A uniquely restricted matching M is maximal if M is not properly contained in any uniquely restricted matching of G. Given a graph G , the Min-Max-UR Matching problem asks to find a maximal uniquely restricted matching in G of minimum cardinality and Decide-Min-Max-UR Matching problem, the decision version of this problem takes a graph G and an integer k and asks whether G admits a maximal uniquely restricted matching of cardinality at most k. It is known that the Decide-Min-Max-UR Matching problem is NP-complete. In this paper, we strengthen this result by proving that the Decide-Min-Max-UR Matching problem remains NP -complete for chordal bipartite graphs, star-convex bipartite graphs, chordal graphs, and doubly chordal graphs. On the positive side, we prove that the Min-Max-UR Matching problem is polynomial time solvable for bipartite distance-hereditary graphs and linear time solvable for bipartite permutation graphs, proper interval graphs, and threshold graphs. Finally, we prove that the Min-Max-UR Matching problem is APX -complete for graphs with maximum degree 4. [ABSTRACT FROM AUTHOR]