Deterministic algorithms for decremental approximate shortest paths: Faster and Simpler

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

In the decremental (1 + ∈)-Approximate Single-Source ShortEst Path (Sssp) Problem, We Are Given a Graph G = (V, E) With n = |V |, m = |E|, Undergoing Edge Deletions, and a Distinguished Source s ∈ V , and We Are Asked to Process Edge Deletions Efficiently and Answer Queries for Distance EsTimates Dist gG(s, v) for Each v ∈ V , At Any Stage, Such That Distg(s, v) ≤ Dist gG(s, v) ≤ (1 + ∈)Distg(s, v). In The DecreMental (1 + ∈)-Approximate All-Pairs Shortest Path (Apsp) Problem, We Are Asked to Answer Queries for Distance EstiMates Dist gG(u, v) for Every u, v ∈ V . In This Article, We Consider The Problems for Undirected, Unweighted Graphs. We Present a New Deterministic Algorithm for The DecreMental (1 + ∈)-Approximate Sssp Problem That Takes Total Update Time O(Mn0.5+o(1)). Our Algorithm Improves On The Currently Best Algorithm for Dense Graphs By Chechik and Bernstein [Stoc 2016] With Total Update Time Õ(n2) and The Best Existing Algorithm for Sparse Graphs With Running Time Õ(n1.25 √m) [Soda 2017] Whenever m = O(n1.5−o(1)). In Order to Obtain Our New Algorithm, We Develop SevEral New Techniques Including Improved Decremental Cover Data Structures for Graphs, a More Efficient Notion of The Heavy/Light Decomposition Framework Introduced By Chechik and Bernstein and The First Clustering Technique to Maintain a Dynamic Sparse Emulator In The Deterministic SetTing. As a By-Product, We Also Obtain a New Simple DeterMinistic Algorithm for The Decremental (1 + ∈)-Approximate Apsp Problem With Near-Optimal Total Running Time Õ(Mn/∈) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].

OriginalsprogEngelsk
Titel31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
RedaktørerShuchi Chawla
ForlagAssociation for Computing Machinery
Publikationsdato2020
Sider2522-2541
ISBN (Elektronisk)9781611975994
StatusUdgivet - 2020
Begivenhed31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, USA
Varighed: 5 jan. 20208 jan. 2020

Konference

Konference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
LandUSA
BySalt Lake City
Periode05/01/202008/01/2020
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics

ID: 250603806