Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
Shiri Chechik, Tianyi Zhang · Society for Industrial and Applied Mathematics eBooks · 2019
Low-stretch spanning tree has been an important graphtheoretic object, as it is one of the building blocks for fast algorithms that solve symmetrically diagonally dominant linear systems, and a significant line of research has been devoted to finding constructions with optimal average stretch. In a very recent work by Goranci and Forster [STOC 2019], the authors initiated the study of low-stretch spanning trees in the dynamic setting, and they proposed a dynamic algorithm that maintains a spanning tree in amortized update time with subpolynomial stretch in an unweighted graph on n vertices undergoing edge insertions and deletions demanded by an oblivious adversary. Our main results are twofold. First, we substantially improve the update time of Goranci and Forster [STOC 2019] from to a subpolynomial of no(1). Second, we generalize our result to weighted graphs under the decremental setting. As far as we know, this is the first non trivial dynamic algorithm for maintaining low-stretch spanning tree for weighted graphs.