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