Approximability results for the maximum and minimum maximal induced matching problems

An induced matching  MM of a graph GG is a set of pairwise non-adjacent edges such that their end-vertices induce a 1-regular subgraph. An induced matching MM is maximal   if no other induced matching contains MM. The Minimum Maximal Induced Matching problem asks for a minimum maximal induced matching in a given graph. The problem is known to be NP-complete. Here we show that, if P≠NP, for any ε>0ε>0, this problem cannot be approximated within a factor of n1−εn1−ε in polynomial time, where nn denotes the number of vertices in the input graph. The result holds even if the graph in question is restricted to being bipartite. For the related problem of finding an induced matching of maximum size (Maximum Induced Matching), it is shown that, if P≠NP, for any ε>0ε>0, the problem cannot be approximated within a factor of n1/2−εn1/2−ε in polynomial time. Moreover, we show that Maximum Induced Matching is NP-complete for planar line graphs of planar bipartite graphs.