Fully Dynamic Biconnectivity in Õ(log² n) Time

We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. Our data structure supports insertion and deletion of edges, as well as queries to whether a pair of connected vertices are either biconnected, or can be separated by a cutvertex, and in the latter case we support access to separating cutvertices. All update operations are supported in amortized O(log² n log² log n) time, and queries take worst-case O(log n log² log n) time. Note that these time bounds match the current best for deterministic dynamic connectivity up to log log n factors.

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.