Simple Algorithms for Fully Dynamic Edge Connectivity

In the fully dynamic edge connectivity problem, the input is a simple graph $G$ undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted $λ_G$. We present two simple randomized algorithms solving this problem. The first algorithm maintains the edge connectivity in worst-case update time $\tilde{O}(n)$ per edge update, matching the known bound but with simpler analysis. Our second algorithm achieves worst-case update time $\tilde{O}(n/λ_G)$ and worst-case query time $\tilde{O}(n^2/λ_G^2)$, which is the first algorithm with worst-case update and query time $o(n)$ for large edge connectivity, namely, $λ_G = ω(\sqrt{n})$.