Fully Dynamic Shortest Paths in Sparse Digraphs

Adam Karczmarz, Piotr Sankowski

Abstract

We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with $\tilde{O}(mn^{4/5})$ worst-case update time processing arbitrary $s,t$-distance queries in $\tilde{O}(n^{4/5})$ time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.
BibTeX
@inproceedings{karczmarz2023fully,
  author = {Adam Karczmarz and Piotr Sankowski},
  title = {{Fully Dynamic Shortest Paths in Sparse Digraphs}},
  booktitle = {ICALP},
  year = {2023},
  url = {https://openreview.net/forum?id=bWKEKRkop3},
}
Figure