EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran Naidu, Janani Sundaresan

Journal of the ACM · 31.08.2026 · 73 (4) · 1-83

DOI: 10.1145/3820493 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 14.08.2026. Verfasst von Sepehr Assadi und 4 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Sloan Research Fellowship, EPSRC New Investigator, EPSRC Doctoral Training Studentship.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A semi-streaming algorithm in dynamic graph streams processes any n -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O(n . polylog( n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds: — We present a randomized sketching based semi-streaming algorithm for O (1)-approximation of maximum matching in dynamic streams using O (log log n ) passes. The approximation ratio of this algorithm can be improved to (1+ɛ) for any fixed ɛ > 0 even on weighted graphs using standard techniques. This exponentially improves upon several O (log n ) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. — We prove that any semi-streaming algorithm (not only sketching based) for O (1)-approximation of maximum matching in dynamic streams requires Ω (log log n ) passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area.

Förderung

  • Sloan Research Fellowship
  • EPSRC New Investigator
  • EPSRC Doctoral Training Studentship
  • Cheriton School of Computer Science, Faculty of Math Graduate Research Excellence Award, and Sepehr Assadi’s NSERC Discovery Grant

Zitieren

APA

Assadi, S., Behnezhad, S., Konrad, C., Naidu, K., & Sundaresan, J. (2026). Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. Journal of the ACM, 73(4), 1-83. https://doi.org/10.1145/3820493

Vancouver

Assadi S, Behnezhad S, Konrad C, Naidu K, Sundaresan J. Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams. Journal of the ACM. 2026;73(4):1-83. doi:10.1145/3820493

BibTeX
@article{Assadi2026,
  author = {Assadi, Sepehr and Behnezhad, Soheil and Konrad, Christian and Naidu, Kheeran and Sundaresan, Janani},
  title = {Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {4},
  pages = {1--83},
  doi = {10.1145/3820493}
}
Kostenlos starten →