Asymptotic performance of the Grimmett-McDiarmid heuristic

Abstract

Grimmett and McDiarmid suggested a simple heuristic for finding stable sets in random graphs. They showed that the heuristic finds a stable set of size $\sim {\log }_{2}n$ (with high probability) on a $G(n,1/2)$ random graph. We determine the asymptotic distribution of the size of the stable set found by the algorithm.

arXiv comment5 pages, 1 figure