2021/09/12 by Julia Chuzhoy, Chuzhoy, Julia · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2109.05621
openalex publication_date 2021/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an n-vertex m-edge graph G with non-negative edge lengths, that undergoes a sequence of edge deletions. The goal is to support approximate shortest-path queries: given a pair x,y of vertices of G, return a path P connecting x to y, whose length is within factor α of the length of the shortest x-y path, in time O(|E(P)|), where α is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems. A long line of work culminated in the algorithm of [Chechik, FOCS 2018] with near optimal guarantees for the oblivious-adversary setting. Unfortunately, adaptive-adversary setting is still poorly understood. For unweighted graphs, the algorithm of [Henzinger, Krinninger and Nanongkai, FOCS '13, SICOMP '16] achieves a (1+ε)-approximation with total update time O(mn/ε); the best current total update time of n2.5+O(ε) is achieved by the deterministic algorithm of [Chuzhoy, Saranurak, SODA'21], with 2O(1/ε)-multiplicative and 2^O(log3/4n/ε)-additive approximation. To the best of our knowledge, for arbitrary non-negative edge weights, the fastest current adaptive-update algorithm has total update time O(n3log L/ε), achieving a (1+ε)-approximation. Here, L is the ratio of longest to shortest edge lengths. Our main result is a deterministic algorithm for decremental APSP in undirected edge-weighted graphs, that, for any Ω(1/loglog m)≤ ε< 1, achieves approximation factor (log m)^2O(1/ε), with total update time O (m1+O(ε)⋅ (log m)O(1/ε2)⋅ log L ).