A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results:

the first data structure to maintain m^o(1)-approximate all-pairs shortest paths (APSP) in an m-edge graph undergoing edge insertions and deletions with worst-case update time m^o(1) and query time Õ(1), and a data structure to maintain a tree T that has diameter no larger than a subpolynomial factor than the underlying graph G that is undergoing edge insertions and deletions where each update is handled in amortized subpolynomial time, and a simpler and more efficient data structure to maintain a (1+є)-approximate single-source shortest paths (SSSP) tree T in a graph undergoing edge deletions in amortized time m^o(1) per update.

All our data structures are deterministic. For the last two data structures, we further have that while the trees T are not subgraphs of G, they do embed with small edge congestion into G. This is in stark contrast to previous approaches and is particularly useful for algorithms that use these data structures internally to route flow along shortest paths. To illustrate the power of our new toolbox, we show that our SSSP data structure can be used directly to give a deterministic implementation of the classic MWU algorithm for approximate undirected minimum-cost flow running in time m^1+o(1). Previously, Bernstein-Gutenberg-Saranurak [FOCS’21] had built a randomized data structure achieving m^1+o(1) time whp. By using our SSSP data structure in the recent almost-linear time algorithm for computing Gomory-Hu trees by Abboud-Li-Panigrahi-Saranurak [FOCS’23], we simplify their algorithm significantly and slightly improve their runtime. To obtain our toolbox, we give the first algorithm that, given a graph G undergoing edge insertions and deletions and a dynamic terminal set A, maintains a vertex sparsifier H that approximately preserves distances between terminals in A, consists of at most |A|m^o(1) vertices and edges, and can be updated in worst-case time m^o(1). Crucially, our vertex sparsifier construction allows us to maintain a low edge-congestion embedding of H into G. This low congestion embedding is needed when using our toolbox in data structures that are then in turn used to implement algorithms routing flows along shortest paths. A concurrent work Chen-Kyng-Liu-Meierhans-Probst Gutenberg [STOC’24] takes our toolbox as the starting point for developing new data structures that solve min-ratio cycle problems on fully dynamic graphs, which in turn leads to the first almost-linear time algorithms for a host of problems on incremental graphs including cycle detection, maintaining SCCs, s-t shortest paths, and minimum-cost flow.