Stochastic Vertex Cover with Few Queries
Soheil Behnezhad, Avrim L. Blum, Mahsa Derakhshan · Society for Industrial and Applied Mathematics eBooks · 2022
We study the minimum vertex cover problem in the following stochastic setting. Let G be an arbitrary given graph, p ∊ (0, 1] a parameter of the problem, and let Gp be a random subgraph that includes each edge of G independently with probability p. We are unaware of the realization Gp, but can learn if an edge e exists in Gp by querying it. The goal is to find an approximate minimum vertex cover (MVC) of Gp by querying few edges of G non-adaptively. This stochastic setting has been studied extensively for various problems such as minimum spanning trees, matroids, shortest paths, and matchings. To our knowledge, however, no non-trivial bound was known for MVC prior to our work. In this work, we present a: (2 + ∊)-approximation for general graphs which queries edges per vertex, and a 1.367-approximation for bipartite graphs which queries poly(1/p) edges per vertex. Additionally, we show that at the expense of a triple-exponential dependence on p–1 in the number of queries, the approximation ratio can be improved down to (1 + ∊) for bipartite graphs. Our techniques also lead to improved bounds for bipartite stochastic matching. We obtain a 0.731-approximation with nearly-linear in 1/p per-vertex queries. This is the first result to break the prevalent (2/3∼ 0.66)-approximation barrier in the poly(1/p) query regime, improving algorithms of [Behnezhad et al., SODA'19] and [Assadi and Bernstein, SOSA'19].