Acyclic Matching in Some Subclasses of Graphs

A subset [Formula: see text] of edges of a graph [Formula: see text] is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called an acyclic matching if G[V(M)], the subgraph of G induced by the M-saturated vertices of G is acyclic. The Acyclic Matching Problem is the problem of finding an acyclic matching of maximum size. The decision version of the Acyclic Matching Problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the decision version of the Acyclic Matching Problem remains NP-complete for comb-convex bipartite graphs and dually-chordal graphs. On the positive side, we present linear time algorithms to compute an acyclic matching of maximum size in split graphs and proper interval graphs. Finally, we show that the Acyclic Matching Problem is hard to approximate within a factor of [Formula: see text] for any [Formula: see text], unless [Formula: see text] and the Acyclic Matching Problem is APX-complete for [Formula: see text]-regular graphs for [Formula: see text], where k is a constant.