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.