{"id":"arxiv:2304.09321","kind":"preprint","title":"A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths","authors":["Julia Chuzhoy","Ruimin Zhang"],"author_count":2,"year":2023,"published":"2023-04-18","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2304.09321","nct_id":null,"source_url":"https://arxiv.org/abs/2304.09321","archive_url":"https://space-kitty.com/papers/arxiv:2304.09321","updated":"2023-04-18","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2304.09321","abstract":"We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted 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/ε)}\\cdot \\log n\\cdot \\log\\log L)$, and query time for shortest-path query is $O(|E(P)|+2^{O(1/ε)}\\cdot \\log n\\cdot \\log\\log L)$, 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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}