Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching

We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. As our main result, we show that this problem can be solved in O(ε^-6) semi-streaming passes, improving the O(ε^-19) pass-complexity obtained by the algorithm of [Fischer, Mitrović, and Uitto, STOC'22]. This significantly progresses toward resolving Open question 2 from [Assadi, SOSA'24]. By utilizing the framework proposed in [FMU'22], our algorithm yields the same round complexity speed-up for computing a (1+ε)-approximate maximum matching in Massively Parallel Computation and CONGEST models.

The data structures our algorithm maintains are phrased in the language of blossoms and represented by alternating trees. This approach essentially allows us to simplify the correctness analysis by effectively treating certain aspects as if they were operating on bipartite graphs, thus circumventing certain technical intricacies appearing in prior work.