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-theart 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 Ω( log n log log n ) 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.