The Taub Faculty of Computer Science Events and Talks

Computing shortest paths is one of the fundamental problems of graph algorithms. The goal of *dynamic* single source shortest paths (SSSP) is to maintain a shortest path tree from a fixed source s as the edges of the graph change over time. The most general case is the fully dynamic one, where each adversarial update inserts or deletes an arbitrary edge. The trivial algorithm is to recompute SSSP after every update in O(m) time. For the fully dynamic case, no non-trivial algorithm is known. We can, however, improve upon the trivial algorithm by restricting the update sequence to be partially dynamic: only insertions (referred to as incremental), or only deletions (referred to as decremental).

In a seminal work, Even and Shiloach [JACM 1981] presented an exact solution to partially dynamic single source shortest path with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+epsilon) algorithm with constant query time and a total update time of ~O(n^2). This was successively improved, with the state of the art achieving ~O(m) total update time. All of these algorithms, however, are randomized. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to ``hide'' these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths.

In this talk I will present the first *deterministic* decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs.

Joint work with Aaron Bernstein