Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

In the dynamic graph stream setting, an algorithm processes a sequence of edge insertions and deletions on an n-vertex graph, often making multiple passes over the data. Of particular interest are semi-streaming algorithms, which operate using a memory of O(n poly log n) bits.

This work addresses the problem of computing a constant-factor approximation to the Maximum Matching problem in the semi-streaming space regime. Previous results have established that at least two passes are necessary, while O(log n /log log n) passes are sufficient. In this talk, we settle the pass complexity for constant-factor approximations to Maximum Matching, proving that Theta(log log n) passes are both necessary and sufficient - an exponential improvement over both the previous best upper and lower bounds.

Our discussion will primarily focus on the new algorithm, which leverages a novel connection between Independent Sets and Matchings. This connection may have broader implications beyond the streaming context.

This is joint work with Sepehr Assadi, Soheil Behnezhad, Kheeran Naidu, and Janani Sundaresan.