hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
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-\frac{1}{2^{O(1/\gamma)}})$ using $n^{1+\gamma}$
time. This improvement over the factor $2$ is, however, minuscule and they
asked if even $1.99$-approximation is possible in $n^{2-\Omega(1)}$ time. We
give a strong affirmative answer to this open problem by showing
$(1.5+\epsilon)$-approximation algorithms that run in
$n^{2-\Theta(\epsilon^{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.
