Even-Shiloach Tree: Variants and Applications to Dynamic Shortest Paths

Even-Shiloach tree refers to a data structure from the classic paper of Even and Shiloach (JACM 1981). It can be thought of as a dynamic version of the breadth-first search tree and has served as a subroutine in many dynamic algorithms for shortest path problems. In this talk, I will present three simple variants of the Even-Shiloach tree and their applications to dynamic shortest paths problems. Applications include the followings.


(1) Truly-subcubic time algorithm for dynamic all-pair shortest paths problem: We obtain an algorithm with a total update time of $\tilde O(n^{5/2})$ and constant query time that has an additive error of two in addition to the $(1+\epsilon)$ multiplicative error. This beats the previous $\tilde O(mn)$ time by Roditty and Zwick (FOCS 2004) when $m=\Omega(n^{3/2})$. Note that the additive error is unavoidable since, even in the static case, an $O(n^{3-\delta})$-time (a so-called truly subcubic) combinatorial algorithm with $(1+\epsilon)$ multiplicative error cannot have an additive error less than $2-\epsilon$, unless we make a major breakthrough for Boolean matrix multiplication and many other long-standing problems. The algorithm can also be turned into a $(2+\epsilon)$-approximation
algorithm (without an additive error) with the same time guarantees, improving
the recent $(3+\epsilon)$-approximation algorithm with $\tilde O(n^{5/2+O(1/\sqrt{\log n})})$ running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees.

(2) Deterministic algorithm for dynamic all-pair shortest paths problem: We obtain a deterministic algorithm with a total update time of $\tilde O(mn)$ and a query time of $O(\log\log n)$. The algorithm has a multiplicative error of $(1+\epsilon)$ and gives the first improved deterministic algorithm since Even and Shiloach published their paper in 1981, which implies $O(mn^2)$ total update time.

(3) Subquadratic time algorithm for dynamic (incremental) single-source shortest paths problem: We obtain the first subquadratic time algorithm for the incremental single source shortest path problem, which also improves the almost-quadratic time implied by the algorithm of Bernstein and Roditty (SODA 2011). Our results also lead to some dynamic distributed algorithms.

Results presented in this talk are based on joint papers with Monika Henzinger and Sebastian Krinninger (University of Vienna).