talks

Date: 13 March 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Peter Kiss
Title: Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time

Abstract:
We show a fully dynamic algorithm for maintaining (1+ε)-approximate size of maximum matching of the graph with n vertices and m edges using m^{0.5−Ω_ε(1)} update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS’13], [Bernstein and Stein SODA’16], [Behnezhad and Khanna SODA’22]). Our key technical component is the first sublinear algorithm for (1,εn)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.