Locally Searching for Large Induced Matchings

Maximilian Fürst, Marilena Leichter, Dieter Rautenbach

It is an easy observation that a natural greedy approach yields a $\left(d-O(1)\right)$-factor approximation algorithm for the maximum induced matching problem in $d$-regular graph…