Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

Soheil Behnezhad

We present a near-tight analysis of the average "query complexity" -- \`a la Nguyen and Onak [FOCS'08] -- of the randomized greedy maximal matching algorithm, improving over the bound of Yoshida, Yamamoto and Ito [STOC'09]. For any $n$-vertex graph of average degree $\bar{d}$, this leads to the following sublinear-time algorithms for estimating the size of maximum matching and minimum vertex cover, all of which are provably time-optimal up to logarithmic factors: $\bullet$ A multiplicative $(2+\epsilon)$-approximation in $\widetilde{O}(n/\epsilon^2)$ time using adjacency list queries. This (nearly) matches an $\Omega(n)$ time lower bound for any multiplicative approximation and is, notably, the first $O(1)$-approximation that runs in $o(n^{1.5})$ time. $\bullet$ A $(2, \epsilon n)$-approximation in $\widetilde{O}((\bar{d} + 1)/\epsilon^2)$ time using adjacency list queries. This (nearly) matches an $\Omega(\bar{d}+1)$ lower bound of Parnas and Ron [TCS'07] which holds for any $(O(1), \epsilon n)$-approximation, and improves over the bounds of [Yoshida et al. STOC'09; Onak et al. SODA'12] and [Kapralov et al. SODA'20]: The former two take at least quadratic time in the degree which can be as large as $\Omega(n^2)$ and the latter obtains a much larger approximation. $\bullet$ A $(2, \epsilon n)$-approximation in $\widetilde{O}(n/\epsilon^3)$ time using adjacency matrix queries. This (nearly) matches an $\Omega(n)$ time lower bound in this model and improves over the $\widetilde{O}(n\sqrt{n})$-time $(2, \epsilon n)$-approximate algorithm of [Chen, Kannan, and Khanna ICALP'20]. It also turns out that any non-trivial multiplicative approximation in the adjacency matrix model requires $\Omega(n^2)$ time, so the additive $\epsilon n$ error is necessary too. As immediate corollaries, we get improved sublinear time estimators for (variants of) TSP and an improved AMPC algorithm for maximal matching.

Knowledge Graph



Sign up or login to leave a comment