Skip to main navigation Skip to search Skip to main content

Fast Deterministic Fully Dynamic Distance Approximation

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain improved dynamic algorithms that, given an unweighted and undirected graph G = (V, E) undergoing edge insertions and deletions, and a parameter 0 < ? = 1, maintain (1 + ?)-approximations of the st-distance between a given pair of nodes s and t, the distances from a single source to all nodes ('SSSP'), the distances from multiple sources to all nodes ('MSSP'), or the distances between all nodes ('APSP'). Our main result is a deterministic algorithm for maintaining (1 + ?)-approximate st-distance with worst-case update time O(n1.407) (for the current best known bound on the matrix multiplication exponent (?). This even improves upon the fastest known randomized algorithm for this problem. Similar to several other well-studied dynamic problems whose state-of-the-art worst-case update time is O(n1.407), this matches a conditional lower bound [BNS, FOCS 2019]. We further give a deterministic algorithm for maintaining (1 + ?)-approximate single-source distances with worst-case update time O(n1.529), which also matches a conditional lower bound. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining (1 + ?, ß)-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improved randomized algorithms for several problems such as exact st-distances and diameter approximation.
Original languageEnglish
Title of host publication2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
Subtitle of host publication[Proceedings]
PublisherIEEE Computer Society
Pages1011-1022
Number of pages12
ISBN (Electronic)9781665455190
ISBN (Print)9781665455206
DOIs
Publication statusPublished - 2022
Externally publishedYes
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: 31 Oct 2022 → 3 Nov 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-October
ISSN (Print)0272-5428

Conference

Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States
CityDenver
Period31/10/22 → 3/11/22

Funding

This research was done while Jan van den Brand was at the Simons Institute for the Theory of Computing and funded by ONR BRC grant N00014-18-1-2562 and by the Simons Institute through a Simons-Berkeley Postdoctoral Fellowship. Sebastian Forster and Yasamin Nazari are supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement No 947702) Th full version is available as [1]. This research was done while Jan van den Brand was at the Simons Institute for the Theory of Computing and funded by ONR BRC grant N00014-18-1-2562 and by the Simons Institute through a Simons-Berkeley Postdoctoral Fellowship. Sebastian Forster and Yasamin Nazari are supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).

FundersFunder number
European Union s Horizon 2020 research and innovation programme
ONR BRCN00014-18-1-2562
Horizon 2020 Framework Programme947702
Simons Institute for the Theory of Computing, University of California Berkeley
European Research Council
Austrian Science FundP 32863-N

    UN SDGs

    This output contributes to the following UN Sustainable Development Goals (SDGs)

    1. SDG 7 - Affordable and Clean Energy
      SDG 7 Affordable and Clean Energy

    Fingerprint

    Dive into the research topics of 'Fast Deterministic Fully Dynamic Distance Approximation'. Together they form a unique fingerprint.

    Cite this