Possible to estimate maximum maximal independent set and minimum maximal independent set?

Hi,

I've got an algorithm which uses a randomly generated graph G as an
input and generates a maximal independent set. What my algorithm
doesn't do is generate a maximal independent set with maximum
cardinality (maximum maximal independent set - MAX-IS) or a maximal
independent set with minimum cardinality (minimum maximal independent
set - MIN-IS).

Now of course it's impossible to get the MAX-IS or MIN-IS of a graph
because it's NP Hard.

However, I would like to evaluate the performance of my algorithm by
comparing it with the MIN-IS and MAX-IS, i.e. how close is the maximal
independent set generated by my algorithm to the MIN-IS/MAX-IS?

So then I'd like to just estimate the MIN-IS and MAX-IS for a graph
made up of "v" uniformly distributed vertices with an average degree of

"d".

My guess is that the cardinality of the MIN-IS is ~ v/d. Is that
correct?

But I'm not sure how to go about computing the cardinality of the
MAX-IS.

Would appreciate any comments.

Cheers,
Sam

.

Relevant Pages