Fully-dynamic minimum spanning forest with improved worst-case update time

We give a Las Vegas data structure which maintains a minimum spanning forest in an n -vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O ( n 1/2 - c ) worst-case time w.h.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O (√ n ) deterministic worst-case update time of Eppstein et al., a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√ n ). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√ n ) w.h.p.; this data structure has O (1) worst-case query time.

Authors

• Christian Wulff-Nilsen

Keywords

• dynamic graph connectivity
• ynamic minimum spanning forest