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

We present a simple deterministic semi-streaming algorithm that computes a $(1-\epsilon )$-approximate maximum matching in general graphs in $O(1\mathrm{/}{\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{p}\mathrm{o}\mathrm{l}\mathrm{y}(1\mathrm{/}\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\mathrm{/}{\epsilon }^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC’22], $O(1\mathrm{/}{\epsilon }^6)$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP’25], and $O(1\mathrm{/}{\epsilon }^4)$ passes by Izumi, Kitamura, and Yamaguchi~['25].