# New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs

Preprint · Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

- Archive id: arxiv:2001.10751
- Published: 2020-01-29
- arXiv: https://arxiv.org/abs/2001.10751
- Source URL: https://arxiv.org/abs/2001.10751
- PDF: https://arxiv.org/pdf/2001.10751
- Provenance: arxiv

## Abstract

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph $G=(V,E)$ subject to edge insertions and deletions and a source vertex $s\\in V$, and the goal is to maintain the distance $d(s,t)$ for all $t\\in V$. Fine-grained complexity has provided strong lower bounds for exact partially dynamic SSSP and approximate fully dynamic SSSP \[ESA'04, FOCS'14, STOC'15\]. Thus much focus has been directed towards finding efficient partially dynamic $(1+ε)$-approximate SSSP algorithms \[STOC'14, ICALP'15, SODA'14, FOCS'14, STOC'16, SODA'17, ICALP'17, ICALP'19, STOC'19, SODA'20, SODA'20\]. Despite this rich literature, for directed graphs there are no known deterministic algorithms for $(1+ε)$-approximate dynamic SSSP that perform better than the classic ES-tree \[JACM'81\]. We present the first such algorithm. We present a \\emph{deterministic} data structure for incremental SSSP in weighted digraphs with total update time $\\tilde{O}(n^2 \\log W)$ which is near-optimal for very dense graphs; here $W$ is the ratio of the largest weight in the graph to the smallest. Our algorithm also improves over the best known partially dynamic \\emph{randomized} algorithm for directed SSSP by Henzinger et al. \[STOC'14, ICALP'15\] if $m=ω(n^{1.1})$. We also provide improved conditional lower bounds. Henzinger et al. \[STOC'15\] showed that under the OMv Hypothesis, the partially dynamic exact $s$-$t$ Shortest Path problem in undirected graphs requires amortized update or query time $m^{1/2-o(1)}$, given polynomial preprocessing time. Under a hypothesis about finding Cliques, we improve the update and query lower bound for algorithms with polynomial preprocessing time to $m^{0.626-o(1)}$. Further, under the $k$-Cycle hypothesis, we show that any partially dynamic SSSP algorithm with $O(m^{2-ε})$ preprocessing time requires amortized update or query time $m^{1-o(1)}$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.