2026-07-23T22:35:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15481 2024-03-06T10:55:24Z ddc:004 open_access

Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time Chen, Jianer Huang, Qin Kanj, Iyad Li, Qian Xia, Ge streaming algorithms matching parameterized algorithms lower bounds 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 Õ(Wk²) space and with Õ(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 Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jianer Chen and Qin Huang and Iyad Kanj and Qian Li and Ge Xia 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.48 urn:nbn:de:0030-drops-154816 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.48 eng https://creativecommons.org/licenses/by/4.0/legalcode