2023/10/16 by Jianer Chen, Qin Huang, Chen, Jianer +7
Computer Science · #Complexity and Algorithms in Graphs #Caching and Content Delivery #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2310.10815
We present streaming algorithms for the graph k-matching problem in both the insert-only and dynamic models. Our algorithms, with space complexity matching the best upper bounds, have optimal or near-optimal update time, significantly improving on previous results. More specifically, for the insert-only streaming model, we present a one-pass algorithm with optimal space complexity O(k2) and optimal update time O(1), that with high probability computes a maximum weighted k-matching of a given weighted graph. The update time of our algorithm significantly improves the previous upper bound of O(log k), which was derived only for k-matching on unweighted graphs. For the dynamic streaming model, we present a one-pass algorithm that with high probability computes a maximum weighted k-matching in O(Wk2 ⋅ polylog(n) space and with O(polylog(n)) update time, where W is the number of distinct edge weights. Again the update time of our algorithm improves the previous upper bound of O(k2 ⋅ polylog(n)). This algorithm, when applied to unweighted graphs, gives a streaming algorithm on the dynamic model whose space and update time complexities are both near-optimal. Our results also imply a streaming approximation algorithm for maximum weighted k-matching whose space complexity matches the best known upper bound with a significantly improved update time.