# A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size

Authors: Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
Conference: The 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).


In the case that the graph is dense, that is, the number of edges is $\Theta(n^2)$, we consider another model, in which the algorithm may ask, for any pair of vertices $u$ and $v$, whether there is an edge between $u$ and $v$. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a $(2,\eps)$-estimate of the size of a minimum vertex cover whose query complexity and running time are $\tilde O(n) \cdot \poly(1/\eps)$.

Full paper: [PDF] [PS]
BibTeX: [DBLP]