# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2212.00189.pdf

(Preprint), 445KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bhattacharya, S., Kiss, P., & Saranurak, T. (2022). Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching. Retrieved from https://arxiv.org/abs/2212.00189.

Cite as: https://hdl.handle.net/21.11116/0000-000C-2696-0

##### 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.

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.