Deterministic algorithms for decremental approximate shortest paths: Faster and Simpler

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 ^g_G(s, v) for Each v ∈ V , At Any Stage, Such That Dist_g(s, v) ≤ Dist ^g_G(s, v) ≤ (1 + ∈)Dist_g(s, v). In The DecreMental (1 + ∈)-Approximate All-Pairs Shortest Path (Apsp) Problem, We Are Asked to Answer Queries for Distance EstiMates Dist ^g_G(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(Mn^0.5+o⁽¹⁾). Our Algorithm Improves On The Currently Best Algorithm for Dense Graphs By Chechik and Bernstein [Stoc 2016] With Total Update Time Õ(n²) and The Best Existing Algorithm for Sparse Graphs With Running Time Õ(n^{1.25 √}m) [Soda 2017] Whenever m = O(n^1.5−o⁽¹⁾). 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].