A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edgeweighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter ǫ, achieves approximation factor (log log n) 2 O(1/ǫ 3 ) , and has amortized update time O(n ǫ log L) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2 O(1/ǫ) • log n • log log L), and query time for shortest-path query is , where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting. In order to obtain these results, we consider an intermediate problem, called Recursive Dynamic Neighborhood Cover (RecDynNC), that was formally introduced in [Chuzhoy, STOC '21]. At a high level, given an undirected edge-weighted graph G undergoing an online sequence of edge deletions, together with a distance parameter D, the goal is to maintain a sparse D-neighborhood cover of G, with some additional technical requirements. Our main technical contribution is twofolds. First, we provide a black-box reduction from APSP in fully dynamic graphs to the RecDynNC problem. Second, we provide a new deterministic algorithm for the RecDynNC problem, that, for a given precision parameter ǫ, achieves approximation factor (log log m) 2 O(1/ǫ 2 ) , with total update time O(m 1+ǫ ), where m is the total number of edges ever present in G. This improves the previous algorithm of [Chuzhoy, STOC '21], that achieved approximation factor (log m) 2 O(1/ǫ) with similar total update time. Combining these two results immediately leads to the deterministic algorithm for fully-dynamic APSP with the guarantees stated above.