On the complexity of minimum maximal acyclic matchings

Abstract 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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -complete. In this paper, we strengthen this result by proving that the decision version of Low-Acy-Matching remains $${\textsf{NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> -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 }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:msup> </mml:math> for any $$\epsilon &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> unless $${\textsf{P}}={\textsf{NP}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>=</mml:mo> <mml:mi>NP</mml:mi> </mml:mrow> </mml:math> . Finally, we establish that Low-Acy-Matching exhibits $$\textsf{APX}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>APX</mml:mi> </mml:math> -hardness when restricted to 4-regular graphs.