Fully Dynamic c-Edge Connectivity in Subpolynomial Time.
Wenyu Jin, Xiaorui Sun · arXiv (Cornell University) · 2020
We present a deterministic fully dynamic algorithm for $c$-edge connectivity problem with $n^{o(1)}$ worst case update and query time for any positive integer $c = (\log n)^{o(1)}$ for a graph with $n$ vertices. Previously, only polylogarithmic, $O(\sqrt{n})$, and $O(n^{2/3})$ worst case update time algorithms were known for fully dynamic $1$, $2$ and $3$-edge connectivity problems respectively. Our techniques include a multi-level $c$-edge connectivity sparsifier, an online-batch update algorithm for the sparsifier, and a general approach to turn an online-batch dynamic algorithm with small amortized update time into a fully dynamic algorithm with worst case update time.