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.