Almost-Linear Time Algorithms for Partially Dynamic Graphs
Host
Rahul Ilango
MIT
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 resolves numerous well-studied problems on such partially dynamic graphs almost-optimally. These 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. In this problem, one is given a fixed demand vector and a threshold $F$, and tasked with reporting the first time a flow of cost $F$ exists or ceases to exist for insertions and deletions respectively.
We give separate algorithms for solving this problem in the incremental and the decremental case. Both follow the L1-IPM framework introduced as part of the first almost linear time minimum-cost flow algorithm [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS'22]. For handling edge insertions, we develop new powerful data structures [Kyng-Meierhans-Probst Gutenberg, STOC'24] to solve the central min-ratio cycle problem against a general adversary [Chen-Kyng-Liu-Meierhans-Probst-Gutenberg, STOC'24]. For handling edge deletions, we take the dual perspective. This leads us to a min-ratio cut problem, which we solve by constructing a dynamic tree that approximately preserves all cuts [van den Brand-Chen-Kyng-Liu-Meierhans-Probst Gutenberg-Sachdevea, FOCS'24].
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 resolves numerous well-studied problems on such partially dynamic graphs almost-optimally. These 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. In this problem, one is given a fixed demand vector and a threshold $F$, and tasked with reporting the first time a flow of cost $F$ exists or ceases to exist for insertions and deletions respectively.
We give separate algorithms for solving this problem in the incremental and the decremental case. Both follow the L1-IPM framework introduced as part of the first almost linear time minimum-cost flow algorithm [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS'22]. For handling edge insertions, we develop new powerful data structures [Kyng-Meierhans-Probst Gutenberg, STOC'24] to solve the central min-ratio cycle problem against a general adversary [Chen-Kyng-Liu-Meierhans-Probst-Gutenberg, STOC'24]. For handling edge deletions, we take the dual perspective. This leads us to a min-ratio cut problem, which we solve by constructing a dynamic tree that approximately preserves all cuts [van den Brand-Chen-Kyng-Liu-Meierhans-Probst Gutenberg-Sachdevea, FOCS'24].