Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Soheil Behnezhad · 2022
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:11The$\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]$.