Abstract | We investigate the existence and efficient algorithmic construction of close to opti-
mal independent sets in random models of intersection graphs. In particular, (a) we
propose a new model for random intersection graphs (Gn,m,~p) which includes the
model of [10] (the “uniform” random intersection graphs model) as an important
special case. We also define an interesting variation of the model of random intersec-
tion graphs, similar in spirit to random regular graphs. (b) For this model we derive
exact formulae for the mean and variance of the number of independent sets of size
k (for any k) in the graph. (c) We then propose and analyse three algorithms for
the efficient construction of large independent sets in this model. The first two are
variations of the greedy technique while the third is a totally new algorithm. Our
algorithms are analysed for the special case of uniform random intersection graphs.
Our analyses show that these algorithms succeed in finding close to optimal in-
dependent sets for an interesting range of graph parameters. |