Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab · 2023
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.