Approximating the Minimum Maximal Independence Number

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.
We consider the problem of approximating the size of a minimum non-extendible independent set of a graph, also known as the minimum dominating independence number. We strengthen a result of Irving to show that there is no constant eps > 0 for which this problem can be approximated within a factor of n^{1-eps} in polynomial time, unless P = NP. This is the strongest lower bound we are aware of for polynomial-time approximation of an unweighted NP-complete graph problem.