Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, Monika Rauch Henzinger · Society for Industrial and Applied Mathematics eBooks · 2021
We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for a weighted, undirected graph G with n nodes and at most m edges undergoing edge insertions and deletions. The goal in this problem is to maintain a tree containing all nodes of G with a randomized algorithm such that for every edge (u, v) of G the expected length of the path from u to v in the tree exceeds the weight of the edge (u, v) only by a small multiplicative factor, called the stretch of the embedding. In this paper, we obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch O(log4 n) with update time m1/2+o(1) or a tree of expected stretch no(1) with update time no(1) (for edge weights polynomial in n). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA '20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design as our trade-off from above carries over to these two problems with minor overheads. For dynamic distance oracles, our result is the first to break the update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, we expect our result to have further applications in dynamic approximation algorithms. From a technical perspective, we obtain our main result by first designing a decremental (i.e., deletionsonly) algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal's ball-growing approach [FOCS ‘96] with the pruning framework of Chechik and Zhang [SODA ‘20]. Such a low-diameter decomposition is the heart of Bartal's seminal tree embedding construction and we show how to adapt it to the decremental setting. We then extend this to a fully dynamic algorithm by significantly enriching a well-known “decremental to fully dynamic” reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction. By additionally exploiting certain properties of our tree embedding, this bootstrapping scheme can be made highly efficient.