Title: Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time,
Abstract: We present a Las Vegas algorithm for dynamically maintaining a minimum
spanning forest of an $n$-node graph undergoing edge insertions and deletions.
Our algorithm guarantees an $O(n^{o(1)})$ worst-case update time with high
probability. This significantly improves the two recent Las Vegas algorithms by
Wulff-Nilsen [STOC'17] with update time $O(n^{0.5-\epsilon})$ for some constant
$\epsilon>0$ and, independently, by Nanongkai and Saranurak [STOC'17] with
update time $O(n^{0.494})$ (the latter works only for maintaining a spanning
forest).
Our result is obtained by identifying the common framework that both two
previous algorithms rely on, and then improve and combine the ideas from both
works. There are two main algorithmic components of the framework that are
newly improved and critical for obtaining our result. First, we improve the
update time from $O(n^{0.5-\epsilon})$ in Wulff-Nilsen [STOC'17] to
$O(n^{o(1)})$ for decrementally removing all low-conductance cuts in an
expander undergoing edge deletions. Second, by revisiting the "contraction
technique" by Henzinger and King [1997] and Holm et al. [STOC'98], we show a
new approach for maintaining a minimum spanning forest in connected graphs with
very few (at most $(1+o(1))n$) edges. This significantly improves the previous
approach in [Wulff-Nilsen STOC'17] and [Nanongkai and Saranurak STOC'17] which
is based on Frederickson's 2-dimensional topology tree and illustrates a new
application to this old technique.