Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation

We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph and G is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G using a small number of queries. Our main result is designing an algorithm that returns a vertex cover of G with size at most (3/2 + ε) times the expected size of the minimum vertex cover, using only O(n/εp) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum and Derakhshan [SODA'22] who also show that Ω(n/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 upperbound with a tight 3/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations.