arXiv · Oct 15, 2026
Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach
By Tatsuya Terao
We present a simple deterministic semi-streaming algorithm that computes a (1-ε)-approximate maximum matching in general graphs in O(1/ε²) 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 budgeted price approach, is very different from the previous poly(1/ε)-pass semi-streaming algorithms for (1-ε)-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use O(1/ε¹⁹) passes by Fischer, Mitrovi'c, and Uitto~[STOC'22], O(1/ε⁶) passes by Mitrovi'c, Mukherjee, Sankowski, and Sheu~[ICALP'25], and O(1/ε⁴) passes by Izumi, Kitamura, and Yamaguchi~['25].