Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch

Abstract

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time. Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than no(1) update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.