Dynamic Matching and (Ordered) Ruzsa-Szemerédi Graphs: Towards Constructive Matching Sparsifiers

Given a graph G, we say a subgraph H of G is a matching sparsifier of G if it preserves large matchings in any induced subgraph of G. In 2012, after formalizing this notion of matching sparsifiers, Goel, Kapralov, and Khanna (GKK) proved existence of a sparse matching sparsifier for any bipartite graph, provided that a certain class of graphs known as Ruzsa-Szemeredi (RS) graphs cannot be too dense. The proof of GKK is non-constructive and does not lead to an efficient (say polynomial time) algorithm for constructing matching sparsifiers.

In this talk, I will describe some approaches to get around this problem and design conditionally fast dynamic algorithms for approximate matchings. My focus will be particularly on the fully dynamic setting where the graph undergoes a sequence of edge insertions and deletions, and the goal is to efficiently maintain an approximate maximum matching of the graph.

Based on:
“Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs” (FOCS’24) joint with Alma Ghafari
“On Regularity Lemma and Barriers in Streaming and Dynamic Matching” (STOC’23) joint with Sepehr Assadi, Sanjeev Khanna, and Huan Li\