Optimal Hardness of Online Algorithms for Large Independent Sets

David Gamarnik, Eren C. Kızıldağ, Lutz Warnke

We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph $G(n,p)$. For constant $p$ and $b=1/(1-p)$, the largest independent set has…