Stochastic Vertex Cover with Few Queries
share
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 G_p be a random subgraph that includes each edge of G independently with probability p. We are unaware of the realization G_p, but can learn if an edge e exists in G_p by querying it. The goal is to find an approximate minimum vertex cover (MVC) of G_p 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 O(1/ϵ^3 p) 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].
READ FULL TEXT