Fully dynamic biconnectivity in Õ(log² n) time

Speaker(s)

Marek Sokołowski

Affiliation

Max Planck Institute for Informatics

Language of the talk

English

Date

Feb. 28, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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 cut-vertex, and in the latter case we support access to separating cut-vertices. All update operations are supported in amortized O(log² n (log log n)²) time in the Word RAM model, and queries take worst-case O(log n (log log n)²) time. Note that these time bounds match the current best for 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) algorithm by Holm, de Lichtenberg, and Thorup [STOC’98].

During this talk, we will sketch how to obtain the improved running time via a series of reductions from the original problem into progressively simpler data structure problems. We will feature the top trees data structure maintaining fully dynamic forests and – time permitting – various biased tree data structures.

Joint work with Jacob Holm, Wojciech Nadara, and Eva Rotenberg.

---