2026-07-24T18:32:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23496 2025-10-02T12:56:53Z ddc:004 open_access

Faster Semi-Streaming Matchings via Alternating Trees Mitrović, Slobodan Mukherjee, Anish Sankowski, Piotr Sheu, Wen-Horng streaming algorithms approximation algorithms maximum matching We design a deterministic algorithm for the (1+ε)-approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in O(ε^{-6}) semi-streaming passes, improving upon the O(ε^{-19}) pass-complexity algorithm by [Fischer, Mitrović, and Uitto, STOC'22]. This contributes substantially toward resolving Open question 2 from [Assadi, SOSA'24]. Leveraging the framework introduced in [FMU'22], our algorithm achieves an analogous round complexity speed-up for computing a (1+ε)-approximate maximum matching in both the Massively Parallel Computation (MPC) and CONGEST models. The data structures maintained by our algorithm are formulated using blossom notation and represented through alternating trees. This approach enables a simplified correctness analysis by treating specific components as if operating on bipartite graphs, effectively circumventing certain technical intricacies present in prior work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Slobodan Mitrović and Anish Mukherjee and Piotr Sankowski and Wen-Horng Sheu 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.119 urn:nbn:de:0030-drops-234965 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.119 eng https://creativecommons.org/licenses/by/4.0/legalcode