Fully Dynamic Shortest Paths in Sparse Digraphs

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}(m{n}^{4\mathrm{/}5})$ worst-case update time processing arbitrary $s,t$-distance queries in $\tilde{O}(n^{4\mathrm{/}5})$ time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.