An Optimal Algorithm for Stochastic Vertex Cover
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G∗ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the base graph G and the probability p as inputs, but its only access to the realized graph G∗ is through queries on individual edges in G that reveal the existence (or not) of the queried edge in G∗. In this paper, we resolve the central open question for this problem: to find a (1+ϵ)-approximate vertex cover using only Oϵ(n/p) edge queries. Prior to our work, there were two incomparable state-of-the-art results for this problem: a (3/2+ϵ)-approximation using Oϵ(n/p) queries (Derakhshan, Durvasula, and Haghtalab, 2023) and a (1+ϵ)-approximation using Oϵ((n/p)· RS(n)) queries (Derakhshan, Saneian, and Xun, 2025), where RS(n) is known to be at least 2ω(logn/loglogn) and could be as large as n/2(log∗ n). Our improved upper bound of Oϵ(n/p) matches the known lower bound of ω(n/p) for any constant-factor approximation algorithm for this problem (Behnezhad, Blum, and Derakhshan, 2022). A key tool in our result is a new concentration bound for the size of minimum vertex cover on random graphs, which might be of independent interest.
