Stochastic Minimum Vertex Cover in General Graphs: a $3\mathrm{/}2$-Approximation

Our main result is designing an algorithm that returns a vertex cover of ${\mathcal{G}}^{\star }$ with size at most $(3\mathrm{/}2+\epsilon )$ times the expected size of the minimum vertex cover, using only $O(n\mathrm{/}\epsilon p)$ non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum, and Derakhshan [SODA’22], who also show that $\mathrm{\Omega }(n\mathrm{/}p)$ queries are necessary to achieve any constant approximation. Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upper bound with a tight $3\mathrm{/}2$-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations.