Paper ID: 7369
On the approximability of the maximum induced matching problem
Journal of Discrete Algorithms, volume 3, no. 1
Page Numbers : 79-91
Publisher: Elsevier Science
URL: This publication is available at this URL.
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.
Keywords: Induced matching; Strong matching; Regular graph; Approximation algorithm; APX-completeness