Seminar Details

The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph $G^\star$ that is realized by sampling each edge independently with some probability $p \in (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^\star$ is through queries on individual edges in $G$ that reveal the existence (or not) of the queried edge in $G^\star$. In this paper, we resolve the central open question for this problem: to find a $(1+\varepsilon)$-approximate vertex cover using only $O_{\varepsilon}(n/p)$ edge queries. Prior to our work, there were two incomparable state-of-the-art results for this problem: a $(3/2+\eps)$-approximation using $O_{\varepsilon}(n/p)$ queries (Derakhshan, Durvasula, and Haghtalab, 2023)  and a $(1+\eps)$-approximation using $O_{\varepsilon}((n/p)\cdot \mathrm{RS}(n))$ queries (Derakhshan, Saneian, and Xun, 2025), where $\mathrm{RS}(n)$ is known to be at least $2^{\Omega\left(\frac{\log n}{\log \log n}\right)}$ and could be as large as $\frac{n}{2^{\Theta(\log^* n)}}$. Our improved upper bound of $O_{\varepsilon}(n/p)$ matches the known lower bound of $\Omega(n/p)$ for any constant-factor approximation algorithm for this problem (Behnezhad, Blum, and Derakhshan, 2022).