Improved fast algorithm finds near-best matches in large networks
Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach
Data Structures and Algorithms
Summary
Finding the largest possible set of pairs in a network, known as a maximum matching, is a key problem for connecting things efficiently. Previous methods to find almost-best matches in big graphs needed lots of repeated passes over the data, making them slow. The authors introduce a new simpler and faster approach called the budgeted price method that requires far fewer passes, especially in general networks. This matches the efficiency of the best known methods for a simpler type of network and answers an open question in the field.
What this means in practice
- •For network engineers: Use efficient algorithms to quickly find near-optimal link pairings in large communication or transportation graphs with limited memory.
- •For social network analysts: Enable faster processing of large social graphs to identify strong matching clusters during streaming data analysis.
Authors
Tatsuya Terao
Abstract
We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{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/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].