2023/04/14 by Anastasiia Alokhina, Jan van den Brand, Alokhina, Anastasiia +1 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2304.07403
openalex publication_date 2023/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Algebraic data structures are the main subroutine for maintaining distances in fully dynamic graphs in subquadratic time. However, these dynamic algebraic algorithms generally cannot maintain the shortest paths, especially against adaptive adversaries. We present the first fully dynamic algorithm that maintains the shortest paths against an adaptive adversary in subquadratic update time. This is obtained via a combinatorial reduction that allows reconstructing the shortest paths with only a few distance estimates. Using this reduction, we obtain the following: On weighted directed graphs with real edge weights in [1,W], we can maintain (1+ε) approximate shortest paths in O(n1.816ε-2 log W) update and O(n1.741 ε-2 log W) query time. This improves upon the approximate distance data structures from [v.d.Brand, Nanongkai, FOCS'19], which only returned a distance estimate, by matching their complexity and returning an approximate shortest path. On unweighted directed graphs, we can maintain exact shortest paths in O(n1.823) update and O(n1.747) query time. This improves upon [Bergamaschi, Henzinger, P.Gutenberg, V.Williams, Wein, SODA'21] who could report the path only against oblivious adversaries. We improve both their update and query time while also handling adaptive adversaries. On unweighted undirected graphs, our reduction holds not just against adaptive adversaries but is also deterministic. We maintain a (1+ε)-approximate st-shortest path in O(n1.529 / ε2) time per update, and (1+ε)-approximate single source shortest paths in O(n1.764 / ε2) time per update. Previous deterministic results by [v.d.Brand, Nazari, Forster, FOCS'22] could only maintain distance estimates but no paths.