APPROXIMATING THE MINIMUM MAXIMAL INDEPENDENCE NUMBER

We consider the problem of approximating the size of a minimum non-ext endible independent set of a graph, also known as the minimum dominati ng independence number. We strengthen a result of Irving to show that there is no constant epsilon > 0 for which this problem can be approxi mated within a factor of n1-epsilon 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.