Uniquely Restricted Matchings in Interval Graphs
Mathew C. Francis, Dalu Jacob, Satyabrata Jana · SIAM Journal on Discrete Mathematics · 2018
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic, Hirst, and Lewenstein [ Algorithmica, 31 (2001), pp. 139--154]. Our algorithm actually solves the more general problem of computing a maximum cardinality “weak independent set” in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.