Minimum Maximal Acyclic Matching in Proper Interval Graphs

Given a graph G, Min-Max-Acy-Matching is the problem of finding a maximal matching M in G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of Min-Max-Acy-Matching is known to be $$\textsf{NP}$$ -complete even for planar perfect elimination bipartite graphs. In this paper, we give the first positive algorithmic result for Min-Max-Acy-Matching by presenting a linear-time algorithm for computing a minimum cardinality maximal acyclic matching in proper interval graphs.