Large independent sets in random regular graphs
We present algorithmic lower bounds on the size s(d) of the largest independent sets of vertices in random d-regular graphs, for each fixed d >= 3. For instance, for d = 3 we prove that, for graphs on n vertices, s(d) >= 0.43475n with probability approaching one as n tends to infinity. (C) 2009 Published by Elsevier B.V.
independent sets random graphs approximation algorithms