Seminar • Algorithms and Complexity • Stochastic Minimum Vertex Cover with Few Queries: A 3/2-approximation

Please note: This seminar will take place in DC 3317 and online.

Mahsa Derakhshan, Assistant Professor
Khoury College of Computer Sciences, Northeastern University

In this talk, we discuss the stochastic vertex cover problem. In this problem, G is an arbitrary known graph, and G* is an unknown random subgraph of G containing each of its edges independently with a known 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.

In this talk, we present a 3/2-approximation algorithm using only O(n/p) non-adaptive queries. This is an improvement over the prior 2-approximation algorithm by Behnezhad et al., who also show that Ω(n/p) queries are necessary to achieve any constant approximation. We will also discuss how this result can be extended to instances where edge realizations are not fully independent. We complement this upper bound with a tight 3/2-approximation lower bound for stochastic graphs whose edge realizations demonstrate mild correlations.

To attend this seminar in person, please go to DC 3317. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/99697289548.