Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Chen, J.; Kanj, I.; Huang, Q.; Li, Q.; Xia, Ge

Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time

Abstract

We present streaming algorithms for the graph k-matching problem in both the insert-only and dynamic models. Our algorithms, while keeping the space complexity matching the best known upper bound, 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 randomized algorithm that runs in optimal 𝒪(k²) space and has optimal 𝒪(1) update time, and that, w.h.p. (with high probability), computes a maximum weighted k-matching of a weighted graph. Previously, the best upper bound on the update time was 𝒪(log k), which was achieved by a deterministic streaming algorithm that however only works for unweighted graphs [Stefan Fafianie and Stefan Kratsch, 2014]. For the dynamic streaming model, we present a one-pass randomized algorithm that, w.h.p., computes a maximum weighted k-matching of a weighted graph in Õ(Wk²) space and with Õ(1) update time, where W is the number of distinct edge weights. Again the update time of our algorithm improves the previous best upper bound Õ(k²) [Rajesh Chitnis et al., 2016]. Moreover, we prove that in the dynamic streaming model, any randomized streaming algorithm for the problem requires k²⋅ Ω(W(log W+1)) bits of space. Hence, both the space and update-time complexities achieved by our algorithm in the dynamic model are near-optimal. A streaming approximation algorithm for k-matching is also presented, whose space complexity matches the best known upper bound with a significantly improved update time.

Title	Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time
Creator	Chen, J.
	Kanj, I.
	Huang, Q.
	Li, Q.
	Xia, Ge
Publisher	International Symposium on Algorithms and Computation (ISAAC 2021)
Academic Department	Computer Science
Division	Natural Sciences
Organization	Lafayette College
Date Issued	2021
Date Available	2021-12-21
Type	Part of Book
Language	English
Keyword	parameterized algorithms
	lower bounds
	streaming algorithms
	matching
Bibliographic Citation	Chen, J., et al. (2021) “Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time.” In Hee-Kap Ahn and Kunihiko Sadakane (eds.), International Symposium on Algorithms and Computation (ISAAC 2021) (Article 48). Dagstuhl Publishing.
Standard Identifier	DOI 10.4230/LIPIcs.ISAAC.2021.48
Standard Identifier	Handle 10385/8623j016z
Permalink	http://hdl.handle.net/10385/8623j016z
Rights Statement	Creative Commons - Attribution
Rights Holders	Chen, J.
	Kanj, I.
	Huang, Q.
	Li, Q.
	Xia, Ge