Stochastic Minimum Vertex Cover with Few Queries: a 3/2-approximation

In this talk, we discuss the stochastic vertex cover problem. In this problem, G is an arbitrary known graph, and G* is an unknown random subgraph of G containing each of its edges independently with a known 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.
In this talk, we present a 3/2-approximation algorithm using only O(n/p) non-adaptive queries. This is an improvement over the prior 2-approximation algorithm by Behnezhad et al., who also show that Ω(n/p) queries are necessary to achieve any constant approximation. We will also discuss how this result can be extended to instances where edge realizations are not fully independent. We complement this upper bound with a tight 3/2-approximation lower bound for stochastic graphs whose edge realizations demonstrate mild correlations.