Simple Algorithms for Fully Dynamic Edge Connectivity

Abstract

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 ${\lambda }_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/{\lambda }_G)$ and worst-case query time $\tilde{O}(n^2/{\lambda }_G^2)$, which is the first algorithm with worst-case update and query time $o(n)$ for large edge connectivity, namely, ${\lambda }_G=\omega (\sqrt{n})$.