Optimal Decremental Connectivity in Non-Sparse Graphs

We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in O(m + npoly log n) total time. Interspersed with the deletions, it can answer queries whether any two given vertices currently belong to the same (2-edge-)connected component in constant time. Our result is based on a general Monte-Carlo randomized reduction from decremental c-edge-connectivity to a variant of fully-dynamic c-edge-connectivity on a sparse graph. For non-sparse graphs with Ω(npoly log n) edges, our connectivity and 2-edge-connectivity algorithms handle all deletions in optimal linear total time, using existing algorithms for the respective fully-dynamic problems. This improves upon an O(mlog(n²/m) + npoly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n²) edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an Ω(log n/log log n) worst-case time lower bound in the decremental setting [Alstrup, Husfeldt, and Rauhe FOCS’98] as well as an Ω(log n) amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC’04].