Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
share
We present a near-tight analysis of the average "query complexity" – à 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 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: ∙ A multiplicative (2+ϵ)-approximation in O(n/ϵ^2) time using adjacency list queries. This (nearly) matches an Ω(n) time lower bound for any multiplicative approximation and is, notably, the first O(1)-approximation that runs in o(n^1.5) time. ∙ A (2, ϵ n)-approximation in O((d̅ + 1)/ϵ^2) time using adjacency list queries. This (nearly) matches an Ω(d̅+1) lower bound of Parnas and Ron [TCS'07] which holds for any (O(1), ϵ 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 Ω(n^2) and the latter obtains a much larger approximation. ∙ A (2, ϵ n)-approximation in O(n/ϵ^3) time using adjacency matrix queries. This (nearly) matches an Ω(n) time lower bound in this model and improves over the O(n√(n))-time (2, ϵ 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 Ω(n^2) time, so the additive ϵ 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.
READ FULL TEXT