Blossoms in the Stream: Simpler and Faster Matchings

15^th April 2026, 13:00 GH223
Anish Mukherjee
University of Liverpool

Abstract

How many passes are really needed to compute a near-maximum matching in a massive graph using only semi-streaming space? I will present a deterministic (1+ε)-approximation algorithm for maximum matching in general graphs that significantly improves the dependence on ε in the number of passes. The algorithm is based on maintaining structured collections of alternating trees and handling blossoms to efficiently capture short augmenting paths. This leads to both an improved bound and a conceptually cleaner framework. The same ideas also yield corresponding improvements in MPC and CONGEST. This is joint work with Slobodan Mitrović, Piotr Sankowski, and Wen-Horng Sheu.