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 + n \operatorname{polylog} n)$ total time. Interspersed with the deletions, it can answer queries to 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 $\Omega(n \operatorname{polylog} 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(m \log (n^2 / m) + n \operatorname{polylog} n)$-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with $\Omega(n^2)$ edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an $\Omega(\log n/\log\log n)$ worst-case time lower bound in the decremental setting [Alstrup, Thore Husfeldt, FOCS'98] as well as an $\Omega(\log n)$ amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC'04].
翻译:我们提出了一个动态算法, 用于维持连接的和2- 连接的组件。 算法是 Monte- Carlo 随机的, 处理以$O( m) + n\ operatorname{polylog} n) 总时值表示的任何边缘删除序列。 在删除中, 它可以解答任何两个给定的顶点是否在固定时间属于同一个连接的组件。 我们的结果基于一个通俗的 Monte- Carlo 随机的削减, 从 deremental $0- edge- 连通性到在稀薄的图上完全动态的 $( m) $( m) $( 美元) 美元- clocal- lidge- 连通性变异性变异性。 对于有 $\ omerga (n) 美元( = 美元) 的 Om- liveralalalalizeralal 时间设置所有最优的线性算算法, 在1999年的 美元( m) 美元( m) 美元( 美元) 美元( 美元) 美元) 内, 美元( 美元) 美元( 美元) 美元) 以内, 美元) 美元(n- 美元) 美元) 美元( 美元) 美元) 的内, 美元( 美元) 美元( 美元) 美元( 美元) 美元) 美元( 美元) 美元) 美元( 美元( 美元) 美元) 美元) 以内算算算算算算算算算算算算的不 的不 的不更低)