  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. While being Monte-Carlo, our reduction supports a certain final
self-check that can be used in Las Vegas algorithms for static problems such as
Unique Perfect Matching.
  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].

Data Structures and Algorithms