Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract)

We present a deterministic fully dynamic algorithm to answer c-edge connectivity queries on pairs of vertices in n°(1) worst case update and query time for any positive integer$c$= (log n)°(1)for a graph with$n$vertices. Previously, only polylogarithmic, O(√n), and O(n2/3) worst case update time fully dynamic algorithms were known for answering 1, 2 and 3-edge connectivity queries respectively [Henzinger-King 1995, Frederikson 1997, Galil and Italiano 1991]. Our result extends the c-edge connectivity vertex sparsifier [Chalermsook et al. 2021] to a multi-level sparsification framework. As our main technical contribution, we present a novel update algorithm for the multi-level c-edge connectivity vertex sparsifier with subpolynomial update time. See https://arxiv.org/abs/2004.07650 for the full version of this paper.