Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2-ε)-Time

We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee em worst-case update time and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing O(√n) bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was O(√n (loglog n)2/log n) [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an O(n0.4+o(1)) worst-case update time, where the o(1) term hides the O(√loglog n/log n) factor. Our second algorithm is Las Vegas and guarantees an O(n0.49306) worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by Kapron et al. To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries.