Options
On the Complexity of Minimum Maximal Acyclic Matchings
Date Issued
01-01-2022
Author(s)
Abstract
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. Min-Max-Acy-Matching is known to be NP -hard. In this paper, we strengthen this result by proving that the decision version of Min-Max-Acy-Matching is NP -complete for planar perfect elimination bipartite graphs. We also prove that Min-Max-Acy-Matching for bipartite graphs cannot be approximated within a ratio of n1-ϵ, for any ϵ> 0 unless P= NP. Finally, we show that Min-Max-Acy-Matching is APX -hard for 4-regular graphs.
Volume
13595 LNCS