Fully Dynamic Edge Connectivity in $\tilde{O}(n^{12/13})$ Time
TL;DR
This work designs a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$ for all values of $\lambda_G$.
Abstract
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $\lambda_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$, for all values of $\lambda_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $\lambda_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\tilde{O}(n^{3/2})$ worst-case update and query time.