New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
© 2020 ACM. 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 sg V, and the goal is to maintain the distance d(s,t) for all tg V. Fine-grained complexity has provided strong lower bounds for exact par...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137818 |
| _version_ | 1811080528362733568 |
|---|---|
| author | Probst Gutenberg, Maximilian Vassilevska Williams, Virginia Wein, Nicole |
| author_facet | Probst Gutenberg, Maximilian Vassilevska Williams, Virginia Wein, Nicole |
| author_sort | Probst Gutenberg, Maximilian |
| collection | MIT |
| description | © 2020 ACM. 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 sg V, and the goal is to maintain the distance d(s,t) for all tg 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 Õ(n2 logW/"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=ω(n1.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 m1/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 m0.626-o(1). Further, under the k-Cycle hypothesis, we show that any partially dynamic SSSP algorithm with O(m2-") preprocessing time requires amortized update or query time m1-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. |
| first_indexed | 2024-09-23T11:33:09Z |
| format | Article |
| id | mit-1721.1/137818 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:33:09Z |
| publishDate | 2021 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1378182022-09-27T20:17:29Z New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs Probst Gutenberg, Maximilian Vassilevska Williams, Virginia Wein, Nicole © 2020 ACM. 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 sg V, and the goal is to maintain the distance d(s,t) for all tg 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 Õ(n2 logW/"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=ω(n1.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 m1/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 m0.626-o(1). Further, under the k-Cycle hypothesis, we show that any partially dynamic SSSP algorithm with O(m2-") preprocessing time requires amortized update or query time m1-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. 2021-11-08T20:26:54Z 2021-11-08T20:26:54Z 2020-06 2021-01-25T17:50:55Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137818 Probst Gutenberg, Maximilian, Vassilevska Williams, Virginia and Wein, Nicole. 2020. "New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs." Proceedings of the Annual ACM Symposium on Theory of Computing. en 10.1145/3357713.3384236 Proceedings of the Annual ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf ACM MIT web domain |
| spellingShingle | Probst Gutenberg, Maximilian Vassilevska Williams, Virginia Wein, Nicole New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title | New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title_full | New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title_fullStr | New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title_full_unstemmed | New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title_short | New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs |
| title_sort | new algorithms and hardness for incremental single source shortest paths in directed graphs |
| url | https://hdl.handle.net/1721.1/137818 |
| work_keys_str_mv | AT probstgutenbergmaximilian newalgorithmsandhardnessforincrementalsinglesourceshortestpathsindirectedgraphs AT vassilevskawilliamsvirginia newalgorithmsandhardnessforincrementalsinglesourceshortestpathsindirectedgraphs AT weinnicole newalgorithmsandhardnessforincrementalsinglesourceshortestpathsindirectedgraphs |