Approximability Results for Induced Matchings in Graphs

An induced matching in a graph G=(V,E) is a set of edges M, no pair of
which are adjacent or joined by an edge in G.  Let MIM be the problem of
finding a maximum induced matching in a graph G.  MIM has applications
in channel assignment, VLSI design and network flow problems.  However
MIM is known to be NP-hard, even if G is d-regular (i.e. each vertex has
degree exactly d).

In this talk we consider the approximability of MIM in d-regular graphs.
We show that, for each d>=3, MIM admits an approximation algorithm with
performance guarantee d-1.  On the other hand, we show that, for the
same class of graphs, MIM does not admit a polynomial-time approximation
scheme unless P=NP.