Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

Abstract

We present a simple deterministic semi-streaming algorithm that computes a $(1-\epsilon )$-approximate maximum matching in general graphs in $O(1/{\epsilon }^2)$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\epsilon )$-pass semi-streaming algorithms for $(1-\epsilon )$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/{\epsilon }^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/{\epsilon }^6)$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/{\epsilon }^4)$ passes by Izumi, Kitamura, and Yamaguchi~['25].

arXiv comment11 pages