On the approximability of the maximum induced matching problem

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d−1 for MIM in d-regular graphs, for each d⩾3. We also prove that MIM is APX-complete in d-regular graphs, for each d⩾3.