2021/12/10 by Soheil Behnezhad, Avrim Blum, Behnezhad, Soheil +3 · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2112.05415
openalex publication_date 2021/12/10 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
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 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].