Deterministic algorithms for decremental approximate shortest paths: Faster and Simpler

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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].

Original languageEnglish
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Publication date2020
Pages2522-2541
ISBN (Electronic)9781611975994
Publication statusPublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: 5 Jan 20208 Jan 2020

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
LandUnited States
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