On the complexity of minimum maximal acyclic matchings

Low-Acy-Matching asks to find a maximal matching M in a given graph G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of Low-Acy-Matching is known to be \({\textsf{NP}}\) $\mathsf{NP}$ -complete. In this paper, we strengthen this result by proving that the decision version of Low-Acy-Matching remains \({\textsf{NP}}\) $\mathsf{NP}$ -complete for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs. We also show the hardness difference between Low-Acy-Matching and Max-Acy-Matching. Furthermore, we prove that, even for bipartite graphs, Low-Acy-Matching cannot be approximated within a ratio of \(n^{1-\epsilon }\) $n^{1-ϵ}$ for any \(\epsilon >0\) $ϵ>0$ unless \({\textsf{P}}={\textsf{NP}}\) $\mathsf{P}=\mathsf{NP}$ . Finally, we establish that Low-Acy-Matching exhibits \(\textsf{APX}\) $\mathsf{APX}$ -hardness when restricted to 4-regular graphs.