Almost-Linear Time Algorithms for Partially Dynamic Graphs

Abstract

A partially dynamic graph is a graph that undergoes edge insertions or deletions, but not both. In this talk, I present a unifying framework that yields the first almost-optimal, almost-linear time algorithms for many well-studied problems on partially dynamic graphs [Chen-Kyng-Liu-Meierhans-Probst-Gutenberg, STOC’24; Brand-Chen-Kyng-Liu-Meierhans-Probst Gutenberg-Sachdevea, FOCS’24]. These problems include cycle detection, strongly connected components, s-t distances, transshipment, bipartite matching, maximum flow, and minimum-cost flow. We achieve this unification by solving the partially dynamic threshold minimum-cost flow problem. We solve these problems by combining a partially dynamic L1 interior point method (Brand-Liu-Sidford STOC’23) with powerful new data structures that solve fully-dynamic APSP and min-cut with sub-polynomial approximation quality and sub-polynomial update and query time.