Fully Dynamic Biconnectivity in Õ(log² n) Time

The previous best algorithm for biconnectivity had an update time of O(log⁴ n log log n) by Thorup [STOC'00], based on the O(log⁵ n) data structure by Holm, de Lichtenberg, and Thorup [STOC'98].

We obtain our improved running time by a series of reductions from the original problem into well-defined data structure problems. While we do indeed apply the well-known techniques for improving running time of two-edge connectivity [STOC'00, SODA'18], surprisingly, these techniques alone do not lead to an update time of Õ(log³ n), let alone the Õ(log² n) we give as a final result.

Our contributions include a formally defined transient expose operation, which can be thought of as a cheaper read-only expose operation on a top tree. For each vertex in the graph, we maintain a data structure over its neighbors, and in this data structure we apply biasing (twice) to save an Õ(log n) factor (twice, so two Õ(log n) factors). One of these biasing techniques is a new, simple biased disjoint sets data structure, which may be of independent interest. Moreover, in this neighborhood data structure, we facilitate that the vertex can select two VIP neighbors that get special treatment, corresponding to its potentially two neighbors on an exposed path, improving an otherwise log n-time operation down to constant time. It is this combination of VIP neighbors with the transient expose operation that saves an Õ(log n)-factor from another bottleneck.

Combining these technical contributions with the well-known techniques for two-edge connectivity [STOC'00, SODA'18], we obtain the desired update times of O(log² n log² log n). The near-linear query time follows directly from the usage of transient expose.

Joint work with Jacob Holm, Wojciech Nadara and Eva Rotenberg. Accepted to STOC '25. Available at https://arxiv.org/abs/2503.21733.