EADS Talk by Aaron Bernstein


An improved deterministic algorithm for dynamic single source shortest paths.


Computing shortest paths in a graph 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 ever 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, or only deletions. For example, in the only-insertions case, we start with an empty graph and the adversary inserts one edge at at a time until we end with some final graph with m edges; the goal is to maintain SSSP throughout this entire sequence of insertions. The trivial algorithm takes O(m) time per update, but as far back as 1981 Even and Shiloach showed how to achieve O(n) time per update. There are conditional lower bounds showing that this O(n) is optimal.

In 2011 Bernstein and Roditty showed that with a (1+eps) approximation we can break through this lower bound: they achieved ~O(n^2/m) update time. This was successively improved, with the state of the art achieving ~O(m^{1/\sqrt{log(n)}}) = m^o(1) update time. All of these algorithms, however, are randomized. Moreover, the randomization forces them to adopt a weaker model with a non-adaptive adversary, which makes these algorithms unsuitable to many settings.

We present a (1+eps)-approximate deterministic algorithm with update time ~O(n^2/m). This does not match the best randomized algorithm, but it is the first deterministic algorithm to beyond O(n). It is also much simpler than all of the above randomized algorithms. Our main tool is an entirely new deterministic scarification technique, which we believe could be applicable to many other deterministic shortest path algorithms.

Appeared at STOC 2016. Joint work with Shiri Chechik.