Heuristics for finding large independent sets, with applications to coloring semi-random graphs

We study a semi-random graph model for finding independent sets. For α>0, an n-vertex graph with an independent set S of site αn is constructed by blending random and adversarial decisions. Randomly and independently with probability p, each pair of vertices, such that one is in S and the other is not, is connected by an edge. An adversary can then add edges arbitrarily (provided that S remains an independent set). The smaller p is, the larger the control the adversary has over the semi-random graph. We design heuristics that with high probability recover S when p>(1+ε)ln n/|S|, for any constant ε>0. We show that when p<(1-ε) In n/|S|, an independent set of size |S| cannot be recovered, unless NP⊆BPP. We use our remits to obtain greatly improved coloring algorithms for the model of k-colorable semi-random graphs introduced by A. Blum and J. Spencer (1995)