Hardness of approximation minimum (or maximum) maximal induced matching graph problems

The minimum (respectively, maximum) maximal induced matching problem asks for a minimum (respectively, maximum) maximal induced matching in a given graph. We show that for any ϵ>0 the minimum maximal induced matching problem for graphs of order n cannot be approximated within a factor of n^1−ϵ in polynomial time, unless P=NP. The result holds even if the graph in question is restricted to be bipartite. For the maximum induced matching problem, it is shown that for any ϵ>0 the problem cannot be approximated within a factor of (n/2)^1−ϵ in polynomial time, unless NP=ZPP. Here ZPP denotes the class of languages decidable by a random expected polynomial-time algorithm that makes no errors (zero-error, probabilistic, polynomial). Moreover, we show that the maximum induced matching problem is NP-complete for the line graphs of bipartite graphs.