New algorithms and hardness for incremental single-source shortest paths in directed graphs

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 ∈ V , and the goal is to maintain the distance d ( s , t ) for all t ∈ 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 deterministic data structure for incremental SSSP in weighted directed graphs with total update time Õ( n 2 log W /є O (1) ) 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 randomized algorithm for directed SSSP by Henzinger et al. [STOC’14, ICALP’15] if m =ω( n 1.1 ). Complementing our algorithm, we 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 new 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) , which is essentially optimal. All previous conditional lower bounds that come close to our bound [ESA’04,FOCS’14] only held for “combinatorial” algorithms, while our new lower bound does not make such restrictions.

Authors

• Maximilian Probst Gutenberg
• Virginia Vassilevska Williams
• Nicole Wein

Keywords

• conditional lower bound
• dynamic algorithm
• shortest path
• single source shortest path