Linear programming based approximation for unweighted induced matchings --- breaking the $\Delta$ barrier

Abstract

A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induced matchings, Discrete Applied Mathematics 243 (2018) 304-310) provide an approximation algorithm with ratio $\Delta$ for the weighted version of the induced matching problem on graphs of maximum degree $\Delta$. Their approach is based on an integer linear programming formulation whose integrality gap is at least $\Delta -1$, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most $\frac{5}{8}\Delta +O(1)$, and that also the approximation ratio can be improved at least to this value. We provide primal-dual approximation algorithms with ratios $(1-\epsilon )\Delta +\frac{1}{2}$ for general $\Delta$ with $\epsilon \approx 0.02005$, and $\frac{7}{3}$ for $\Delta =3$. Furthermore, we prove a best-possible bound on the fractional induced matching number in terms of the order and the maximum degree.