Abstract
We study the problem of estimating the size of maximum matching and minimum vertex cover in sub linear time. Denoting the number of vertices by $n$ and the average degree in the graph by $\overline{d}$ , we obtain the following results for both problems which are all provably time-optimal up to polylogarithmic factors: 1 1 The $\tilde{O}(\cdot)$ notation hides polylog $n$ factors throughout the paper. •A multiplicative $(2+\varepsilon)$ -approximation that takes $\tilde{O}(n/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2,\ \varepsilon n)$ -approximation that takes $\tilde{O}((\overline{d}+1)/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2,\ \varepsilon n)$ -approximation that takes $\tilde{O}(n/\varepsilon^{3})$ time using adjacency matrix queries. Our main contribution and the key ingredient of the bounds above is a near-tight analysis of the average query complexity of randomized greedy maximal matching which improves upon a seminal result of Yoshida, Yamamoto, and Ito $[\text{STOC}^{\prime} 09]$ .

This publication has 17 references indexed in Scilit: