Abstract | We investigate the existence and efficient algorithmic
construction of close to optimal independent sets in random models
of intersection graphs. In particular, (a) we propose \empha new model for random intersection graphs
($G_n, m, \vecp$) which includes the model of
\citeRIG (the ``uniform" random intersection graphs model) as an
important special case. We also define an interesting variation of
the model of random intersection graphs, similar in spirit to
random regular graphs. (b) For this model we derive \emphexact 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 \emphthree 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
\emphclose to optimal independent sets for an interesting range
of graph parameters. |