Major breakthrough in dynamic graph algorithms earns Best Paper

A project solving a major open question in the field of graph algorithms earned a Best Paper Award at the leading algorithms conference ACM-SIAM Symposium on Discrete Algorithms (SODA ’23). Assistant professor in CSE Thatchaphol Saranurak, collaborating with researchers from the University of Warwick and Google Research, combined insights from streaming and sublinear-time algorithms to obtain a surprising result in dynamic algorithms, breaking a long-standing barrier on a central problem of the area.

The team’s study focused on a foundational problem in graph theory, the maximum matching problem. The task is, given a graph, to find the maximum number of edges inside the graph so that they do not share any vertices with each other. The authors describe the problem as a cornerstone of combinatorial optimization and theoretical computer science.

In particular, they looked at this problem in the context of graphs dynamically undergoing changes, such as edges being added or deleted — how do you maintain the (approximate) size of the maximum matching of the graph undergoing edge updates without using too much computation time in between updates? Prior work presented algorithms that can achieve this in sublinear time, meaning computation times that grow in proportion to the size of the graph at a less than linear rate. These algorithms, however, are only feasible for approximate matchings rather than exact, and therefore carry the additional measurement of an approximation ratio indicating how close their solution is to optimal.

The question then became one of how small the approximation ratio could be for a maximum matching algorithm that maintains a sublinear update time. It was first raised in 2010, when the value was stuck at a ratio of 2, and revisited repeatedly since without better results. Saranurak and his collaborators have finally provided a better answer.

The team showed that the long-standing approximation ratio of 2 for dynamic matching in polylog update time can be improved to 1.98, the first algorithm of its kind to break this barrier. In a bipartite graph, the ratio is further improved to 1.71.

“After this,” Saranurak says, “ideas from sublinear-time algorithms should be more prevalent in the future of dynamic matching algorithms.”

This research was published in the paper “Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time,” authored by Sayan Bhattacharya, Peter Kiss (both from the University of Warwick), Thatchaphol Saranurak, and David Wajc (Google Research). It will be presented at SODA ’23 in Florence, Italy, from January 22-25. The Best Paper Award was given jointly to this work and “Dynamic Algorithms for Maximum Matching Size” by researchers from Stanford University.