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 G(s, v) for each v ϵ V, at any stage, such that G(s, v) ≤ G(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 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(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 [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].