Maximal Matching in Bounded-deletion Streams

Explore the intricacies of maximal matching in bounded-deletion graph streams through this 38-minute lecture by Christian Konrad from the University of Bristol, UK. Delve into the study of graphs revealed as sequences of edge insertions and deletions, with a focus on scenarios where deletions are limited to a parameter K. Examine the single-pass streaming space complexity of this problem, known to be Θ(n^2) for unrestricted K, where n represents the number of vertices. Discover a new algorithm and matching lower bound result that provide a comprehensive understanding of how space complexity evolves as a function of K. Gain insights into sublinear graph simplification techniques and their applications in this Simons Institute presentation.