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 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.

Automated summary

This paper investigates the problem of MIN-MAX-ACY-Matching and presents a linear-time algorithm to solve it in proper interval graphs.