2026-07-23T13:52:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22669 2026-04-17T05:32:05Z ddc:004 open_access

Query Complexity of Stochastic Minimum Vertex Cover Derakhshan, Mahsa Saneian, Mohammad Xun, Zhiyang Sublinear algorithms Vertex cover Query complexity We study the stochastic minimum vertex cover problem for general graphs. In this problem, we are given a graph G = (V, E) and an existence probability p_e for each edge e ∈ E. Edges of G are realized (or exist) independently with these probabilities, forming the realized subgraph 𝒢. The existence of an edge in 𝒢 can only be verified using edge queries. The goal of this problem is to find a near-optimal vertex cover of 𝒢 using a small number of queries. Previous work by Derakhshan, Durvasula, and Haghtalab [STOC 2023] established the existence of 1.5 + ε approximation algorithms for this problem with O(n/ε) queries. They also show that, under mild correlation among edge realizations, beating this approximation ratio requires querying a subgraph of size Ω(n ⋅ RS(n)). Here, RS(n) refers to Ruzsa-Szemerédi Graphs and represents the largest number of induced edge-disjoint matchings of size Θ(n) in an n-vertex graph. In this work, we design a simple algorithm for finding a (1 + ε) approximate vertex cover by querying a subgraph of size O(n ⋅ RS(n)) for any absolute constant ε > 0. Our algorithm can tolerate up to O(n ⋅ RS(n)) correlated edges, hence effectively completing our understanding of the problem under mild correlation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mahsa Derakhshan and Mohammad Saneian and Zhiyang Xun 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.41 urn:nbn:de:0030-drops-226691 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.41 eng https://creativecommons.org/licenses/by/4.0/legalcode