On the Parameterized Complexity Of the Acyclic Matching Problem

A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acyclic matching of size $k$ in $G$. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects.  First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter $k$. On the other hand, the problem is fixed parameter tractable with respect to the parameters $tw$ and $(k,c_4)$, where $tw$ and $c_4$ are the treewidth and the number of cycles with length $4$ of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter $k$ for the line graphs and every proper minor-closed class of graphs (including planar graphs).