2022/12/01 by Sayan Bhattacharya, Bhattacharya, Sayan, P. Kiss +3
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2212.00189
openalex publication_date 2022/12/01 · openalex created_date 2022/12/13 · openalex updated_date 2026/07/28
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al.[SODA'23] improved the approximation factor to (2-\frac12O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2-Ω(1) time. We give a strong affirmative answer to this open problem by showing (1.5+ε)-approximation algorithms that run in n^2-Θ(ε2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and streaming [Bernstein ICALP'20] settings, but never before in the sublinear setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23] independently showed sublinear algorithms similar to our Theorem 1.2 in both adjacency list and matrix models. Furthermore, in [BRR'23], they show additional results on strictly better-than-1.5 approximate matching algorithms in both upper and lower bound sides.