# Optimal Decremental Connectivity in Non-Sparse Graphs

Anders Aamand
MIT
<EMAIL_ADDRESS>Adam Karczmarz
University of Warsaw
<EMAIL_ADDRESS>Jakub Łącki
Google Research
<EMAIL_ADDRESS>Nikos Parotsidis
Google Research
<EMAIL_ADDRESS>Peter M. R. Rasmussen
University of Copenhagen
<EMAIL_ADDRESS>Mikkel Thorup
University of Copenhagen
<EMAIL_ADDRESS>
###### Abstract

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{poly}\log 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{poly}\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(m\log(n^{2}/m)+n\operatorname{poly}\log 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].

##  1 Introduction

In this paper, we present Monte Carlo randomized decremental dynamic
algorithms for maintaining the connected and 2-edge-connected components in an
undirected graph subject to edge deletions. Starting from a graph with $n$
nodes and $m$ edges, the algorithm can process any sequence of edge deletions
in $O(m+n\operatorname{polylog}n)$ total time while answering queries whether
a pair of vertices is currently in the same (2-edge-)connected component. Each
query is answered in constant time. The algorithm for decremental 2-edge-
connectivity additionally reports all bridges as they appear.

For some concrete constant $\alpha\leq 7$, our decremental algorithms thus use
$O(m)$ total time on the edge deletions from a graph with $m\geq
n\log^{\alpha}n$ edges, and we will refer to such graphs as _non-sparse_. If
we delete all the edges, we support edge deletions in constant amortized time.
As we shall discuss in Section 1.1, it is not possible to obtain a constant
worst-case time bound for individual edge deletions in this decremental
setting, nor is it possible to obtain a constant amortized time bound for edge
updates in the fully-dynamic version of the connectivity problem.

Our algorithms are Monte Carlo randomized and answer all queries correctly
with high probability111We define high probability as probability
$1-O(n^{-\gamma})$ for any given $\gamma$.. We note that since the correct
answer to each query is uniquely determined from the input, the algorithms
work against adaptive adversaries, that is, each deleted edge may depend on
previous answers to queries222Indeed, the only way to strengthen the adversary
is to reveal information about the internal choices of the algorithm, through
responses to queries..

Furthermore, our algorithms offer a _self-check_ capability. At the end, after
all updates and queries have been processed online, each algorithm can
deterministically check if it might have made a mistake. If the self-check
passes, it is _guaranteed_ that no incorrect answer was given. Otherwise, the
algorithm _may have_ made a mistake. However, as we show in the following, the
self-check passes with high probability. This feature implies that we can
obtain Las Vegas algorithms for certain _non-dynamic_ problems whose solutions
employ decremental (2-edge-)connectivity algorithms as subroutines: we simply
repeat trying to solve the static problem from scratch, each time with new
random bits, until the final self-check is passed. With high probability, we
are done already after the first round. A nice concrete example is the
algorithm of Gabow, Kaplan, and Tarjan [GKT01] for the static problem of
deciding if a graph has a unique perfect matching. The algorithm uses a
decremental 2-edge-connectivity algorithm as a subroutine. With our
decremental 2-edge-connectivity algorithm, repeating until the self-check is
passed, we obtain a Las Vegas algorithm for the unique perfect matching
problem that is always correct, and which terminates in
$O(m+n\operatorname{polylog}n)$ time with high probability.

The tradition of looking for linear time algorithms for non-sparse graphs goes
back at least to Fibonacci heaps, which can be used for solving single source
shortest paths in $O(m+n\log n)$ time [FT87]. Our results show that another
fundamental graph problem can be solved in linear time in the non-sparse case.

The previous best time bounds for the decremental connectivity and 2-edge-
connectivity problems were provided by Thorup [Tho99]. His algorithms run in
$O(m\log(n^{2}/m)+n\operatorname{polylog}n)$ total time. This is $O(m)$ only
for dense graphs with $\Omega(n^{2})$ edges. It should be noted that [Tho99]
used Las Vegas randomization, that is, correctness was guaranteed, but the
running time bound only held with high probability. Our algorithms are Monte
Carlo randomized, but offer the final self-check. Another difference is that
our new algorithms need only a polylogarithmic number of random bits, whereas
the ones from [Tho99] used $\Theta(m)$ random bits.

Both our algorithm and the previous one by Thorup are based on a general
reduction from decremental $c$-edge-connectivity to fully-dynamic $c$-edge-
connectivity on a sparse graph with $\tilde{O}(cn)$ updates. The reductions
have a polylogarithmic cost per node as well as a cost per original edge. Our
contribution is to reduce the edge cost from $O(\log(n^{2}/m))$ to the optimal
$O(1)$. The general reduction and its consequences will be discussed in
Section 1.2.

We will now give a more detailed discussion of our results in the context of
related work.

###  1.1 Connectivity

Dynamic connectivity is the most fundamental dynamic graph problem. The fully
dynamic version has been extensively studied [CGL+19, EGIN97, Fre85, HK99,
HdLT01, HHKP17, KKM13a, KKPT16, NSW17, PD04, PT11, Tho00, Wan15, Wul13] from
both the lower and upper bound perspective, even though close to optimal
amortized update bounds have been known since the 90s [HK99, HdLT01, Tho00].
Currently, the best known amortized update time bounds are (expected)
$O(\log{n}\cdot(\log{\log{n}})^{2})$ using randomization [HHKP17] and
$O(\log^{2}{n}/\log\log{n})$ deterministically [Wul13]. Both these results
have optimal (wrt. to the lower bounds) query time.

##### Connectivity Lower Bounds

Our result implies that decremental connectivity is provably easier than
fully-dynamic connectivity for a wide range of graph densities. Specifically,
let $t_{u}$ be the update time of a fully dynamic connectivity algorithm and
let $t_{q}$ be its query time. Pǎtraşcu and Demaine [PD04] showed a lower
bound of $\Omega(\log n)$ on $\max(t_{u},t_{q})$ in the cell-probe model.
Pǎtraşcu and Thorup [PT11] also showed that $t_{u}=o(\log{n})$ implies
$t_{q}=\Omega(n^{1-o(1)})$. These lower bounds hold for all graph densities
and allow for both amortization and randomization. As a result, no fully-
dynamic connectivity algorithm can answer connectivity queries in constant
time and have an amortized update time of $o(\log n)$.

In sharp contrast, assuming that $m=\Omega(n\operatorname{poly}\log n)$ edges
are deleted, our algorithm shows that one can solve decremental connectivity
handling both queries and updates in constant amortized time.

We note that such a result is possible only because we allow for amortization,
as any decremental connectivity algorithm with _worst-case_ update time
$O(\operatorname{polylog}n)$ must have worst-case query time
$\Omega\left(\frac{\log n}{\log\log n}\right)$ [AHR98]. This lower bound holds
even for trees supporting restricted connectivity queries of the form "are $u$
and $v$ connected?" for a fixed “root” $u$. This lower bound also holds for
dense graphs, as we can always add a large static clique to the problem.

An optimal incremental connectivity algorithm has been known for over 40
years. Namely, to handle $m\geq n$ edge insertion and $q$ connectivity
queries, one can use the union-find data structure [Tar75] with $n-1$ unions
and $2(m+q)$ finds. The total running time is $\Theta((m+q)\alpha((m+q),n))$,
which is linear for all but very sparse graphs (since $\alpha(\Omega(n\log
n),n)=O(1)$). It was later shown that this running time is optimal for
incremental connectivity [FS89].

Similarly to the decremental case, one cannot hope to obtain an analogous
result with a worst-case update time in the incremental setting: Pǎtraşcu and
Thorup [PT11] showed that any incremental connectivity data structure with
$o\left(\frac{\log n}{\log\log n}\right)$ worst-case update time must have
worst-case $\Omega(n^{1-o(1)})$ query time in the cell-probe model.

##### Other cases of optimal decremental connectivity

There is much previous work on cases where decremental connectivity can be
supported in $O(m)$ total time. Alstrup, Secher, and Spork [ASS97] showed that
decremental connectivity can be solved in optimal $O(m)$ total time on
forests, answering queries in $O(1)$ time. This was later extended to other
classes of sparse graphs: planar graphs [LS17], and minor-free graphs [HR18].
All these special graph classes are sparse with $m=O(n)$ edges.

For general graphs, we only have the previously mentioned work by Thorup
[Tho99], yielding a total running time of $O(m)$ for very dense graphs with
$m=\Omega(n^{2})$ edges. We now obtain the same linear time bound for all non-
sparse graphs with $m=\Omega(n\operatorname{poly}\log n)$ edges.

###  1.2 General reduction for $c$-edge-connectivity

Our algorithm for decremental connectivity is based on a general randomized
reduction from decremental $c$-edge-connectivity (assuming all $m$ edges are
deleted) to fully-dynamic $c$-edge-connectivity on a sparse graph with
$\tilde{O}(cn)$ updates. The reduction has a polylogarithmic cost per node as
well as a constant cost per edge. The previous decremental connectivity
algorithm of Thorup [Tho99] was also based on such a general reduction, but
the cost per edge was $O(\log(n^{2}/m))$ which is $O(1)$ only for very dense
graphs with $m=\Omega(n^{2})$. Below we will describe the format of the
reductions in more detail.

Because there are different notions of $c$-edge-connectivity, we first need to
clarify our definitions. We say that two vertices $u,v$ are $c$-edge-connected
iff there exist $c$ edge-disjoint paths between $u$ and $v$ in $G$. It is
known that $c$-edge-connectivity is an equivalence relation; we call its
classes the _$c$ -edge-connected classes_. However, for $c\geq 3$, a $c$-edge-
connected class may induce a subgraph of $G$ which is not connected, so it
also makes sense to consider _$c$ -edge-connected components_, i.e., the
maximal $c$-edge-connected induced subgraphs of $G$.333There is no consensus
in the literature on the terminology relating to $c$-edge-connected components
and classes. Some authors (e.g., [GI93, GI96]) reserve the term $c$-edge-
connected components for what we in this paper call $c$-edge-connected
classes. It is important to note that the $c$-edge-connected components and
the $c$-edge-connected classes are _uniquely defined_ and both induce a
natural partition of the vertices of the underlying graph. Moreover, each
$c$-edge-connected component of $G$ is a subset of some $c$-edge-connected
class of $G$. For $c=1,2$, the $c$-edge-connected classes are $c$-edge-
connected, so the two notions coincide. To illustrate the difference, let us
fix $c\geq 3$ and consider a graph with $c+2$ vertices
$v_{s},v_{t},v_{1},\dots,v_{c}$ and edges
$\\{v_{s},v_{t}\\}\times\\{v_{1},\dots,v_{c}\\}$; while all $c$-edge-connected
components in this graph are singletons, there is one $c$-edge-connected
class, which is not a singleton, namely $\\{v_{s},v_{t}\\}$.

We define a _$c$ -certificate_ of $G$ to be a subgraph $H$ of $G$ that
contains all edges not in $c$-edge-connected components, and a $c$-edge-
connected subgraph of each $c$-edge-connected component. Both Thorup’s and our
reduction maintains a $c$-certificate $H$ of $G$. Then, for any
$c^{\prime}\leq c$, we have that the $c^{\prime}$-edge-connected equivalence
classes and the $c^{\prime}$-edge-connected components are the same in $G$ and
$H$. As the edges from $G$ are deleted, we maintain a $c$-certificate with
$\widetilde{O}(cn)$ edges undergoing only $\widetilde{O}(cn)$ edge insertions
and deletions in total.

The uniquely defined $c$-edge-connected components of a graph may be found by
repeatedly removing cuts of size at most $c-1$. For the reductions, we need
algorithms that can help us in this process. We therefore define the _fully
dynamic $c$-edge-cut problem_ as follows. Suppose a graph $G$ is subject to
edge insertions and/or deletions. Then, a fully dynamic $c$-edge-cut data
structure should maintain any edge $e$ that belongs to some cut of size less
than $c$. A typical application of such a data structure is to repeatedly
remove such edges $e$ belonging to cuts of size less than $c$, which splits
$G$ into its $c$-edge-connected components. For each $c\geq 1$, denote by
$T_{c}(n)$ the amortized time needed by the data structure to find an edge
belonging to a cut of size less than $c$. For example, for $c=1$ we have
$T_{1}(n)=O(1)$ since we do not have to maintain anything. For $c=2$, the data
structure is required to maintain some _bridge_ of $G$ and it is known that
$T_{2}(n)=O((\log{n}\cdot\log\log{n})^{2})$ [HRT18]. For $c\geq 3$, in turn,
we have $T_{c}(n)=O(n^{1/2}\operatorname{poly}{(c)})$ [Tho07].

Given a fully dynamic $c$-edge-cut data structure, whose update time for a
graph on $n$ nodes is $T_{c}(n)$, Thorup’s [Tho99] reduction maintains, in
$O(m\log(n^{2}/m))+\widetilde{O}(c\cdot n\cdot T_{c}(n))$ total time, a
$c$-certificate $H$ of the decremental graph $G$ starting with $n$ nodes and
$m$ edges. The certificate undergoes only $\widetilde{O}(cn)$ edge insertions
and deletions throughout any sequence of deletions issued to $G$. We reduce
here the total time to $O(m)+\widetilde{O}(c\cdot n\cdot T_{c}(n))$.

Combining our reduction with the polylogarithmic fully-dynamic connectivity
and 2-edge-connectivity algorithm of Holm, de Lichtenberg, and Thorup
[HdLT01], we can now solve decremental connectivity and 2-edge-connectivity in
$O(m)+\widetilde{O}(n)$ time.

We can also apply the fully dynamic min-cut algorithm of Thorup [Tho07] which
identifies cuts of size $n^{o(1)}$ in $n^{1/2+o(1)}$ worst-case time. For
$c=n^{o(1)}$, we then maintain a $c$-certificate $H$ in $O(m+n^{3/2+o(1)})$
total time. This includes telling which vertices are in the same $c$-edge-
connected component. If we further want to answer queries about $c$-edge-
connectivity between pairs of nodes, we can apply the fully-dynamic data
structure of Jin and Sun [JS20] to the $c$-certificate $H$. By definition, the
answers to these queries are the same in $H$ and $G$, and the algorithm takes
$n^{o(1)}$ time per update or query. Hence the total time for the updates
remains $O(m+n^{3/2+o(1)})$, and we can tell if two vertices are $c$-edge-
connected in $n^{o(1)}$ time.

####  1.2.1 Results

We will now give a more precise description of our reduction, including the
log-factors hidden in the $\widetilde{O}(cn)$ bound. Let the _decremental
$c$-certificate_ problem be that of maintaining a $c$-certificate of $G$ when
$G$ is subject to edge deletions. Recall that $T_{c}(n)$ denotes the amortized
update time of a fully-dynamic $c$-edge-cut data structure. Thorup [Tho99]
showed the following.

######  Theorem 1.1 (Thorup [Tho99]).

There exists a Las Vegas randomized algorithm for the decremental
$c$-certificate problem with expected total update time
$O(m\log{(n^{2}/m)}+n(c+\log{n})\cdot T_{c}(n)\log^{2}{n})$. The maintained
certificate undergoes $O(n\cdot(c+\log{n}))$ expected edge insertions and
deletions throughout, assuming $\Theta(m)$ random bits are provided. These
bounds similarly hold with high probability.

In particular the total update time is $O(m)$ for very dense graphs with
$\Omega(n^{2})$ vertices. Our main result, which we state below, shows that an
amortized constant update time can be obtained as long as the initial graph
has $\Omega(n\operatorname{polylog}(n))$ edges.

######  Theorem 1.2.

There exists a Monte Carlo randomized algorithm for the decremental
$c$-certificate problem with total update time $O(m+n(c+\log{n})\cdot
T_{c}(n)\log^{3}{n}+nc\log^{7}{n})$. The maintained certificate undergoes
$O(nc\log^{4}{n})$ edge insertions and deletions throughout. The algorithm is
correct with high probability. Within this time bound, the algorithm offers a
final self-check after processing all updates.

In fact, our algorithm is itself a reduction to $O(\log{n})$ instances of the
decremental $c$-certificate problem on a subgraph of $G$ with
$O(m/\log^{2}{n})$ edges. To handle these instances, we use the state-of-the-
art data structure (Theorem 1.1) which costs only $O(m)$ in terms of $m$. As a
result, our improved reduction (Theorem 1.2) requires $\Theta(m)$ random bits
to hold.

However, our new randomized $c$-certificate that is the key to obtaining the
new reduction requires only pairwise independent sampling to work. This is in
sharp contrast with the certificate of Karger [Kar99], used in the
construction of Thorup’s data structure (Theorem 1.1), which requires full
independence, i.e., $\Theta(m)$ random bits. We show that we may instead plug
our new certificate into Thorup’s data structure at the cost of a single
additional logarithmic factor in the running time. Since Karger’s certificate
constitutes the only use of randomness in Thorup’s data structure, and full
independence in our construction is required only for invoking Theorem 1.1, we
obtain the below low-randomness version of our main result.

######  Theorem 1.3.

There exists a Monte Carlo randomized algorithm for the decremental
$c$-certificate problem with total update time $O(m+nc\cdot
T_{c}(n)\log^{4}{n}+nc\log^{7}{n})$. The maintained certificate undergoes
$O(nc\log^{4}{n})$ edge insertions and deletions throughout. The algorithm is
correct with high probability if $O(\operatorname{polylog}{n})$ random bits
are provided. Within this time bound, the algorithm offers the final self-
check after processing all updates.

By using Theorem 1.3 with best known fully dynamic algorithms for different
values of $c$ [HdLT01, JS20, Tho07], we obtain:

######  Theorem 1.4.

There exists Monte Carlo randomized decremental connectivity and decremental
2-edge-connectivity algorithms with $O(m+n\log^{7}{n})$ total update time and
$O(1)$ query time.

######  Theorem 1.5.

Let $c=(\log{n})^{o(1)}$. There exists a Monte Carlo randomized decremental
$c$-edge-connectivity data structure which can answer queries to whether two
vertices are in the same $c$-edge connected class in $O(n^{o(1)})$ time, and
which has $O(m)+\tilde{O}(n^{3/2})$ total update time.

######  Theorem 1.6.

Let $c=O(n^{o(1)})$. There exists a Monte Carlo randomized decremental
$c$-edge-connected components data structure with $O(m+n^{3/2+o(1)})$ total
update time and $O(1)$ query time.

All the above applications of our main result work using only
$O(\operatorname{polylog}{n})$ random bits. They moreover each have the self-
check property as well. As discussed before, our new 2-edge-connectivity data
structure implies an optimal $O(m)$-time unique perfect matching algorithm for
$m=\Omega(n\operatorname{polylog}{n})$.

###  1.3 Adaptive updates and unique perfect matching

All our time bounds are amortized. Amortized time bounds are particularly
relevant for dynamic data structures used inside algorithms solving problems
for static graphs. In such contexts, future updates often depend on answers to
previous queries, and therefore we need algorithms that work with adaptive
updates.

Our reduction works against adaptive updates as long as queries do not reveal
any details about the $c$-certificate $H$. The reduction will safely maintain
the following public information about the $c$-edge-connected components of
$G$: between deletions, each such component will have an ID stored with all
its vertices, so two vertices are in the same $c$-edge-connected component if
and only if they have the same component ID. With the component ID, we store
its size and a list with its vertices in order of increasing vertex ID.
Finally, we can have a list of all edges that are not in $c$-edge-connected
components. After each update, we can also tell what are the IDs of the new
$c$-edge-connected components, and what are the edges between them.

For the case of 2-edge-connectivity, the above means that we can maintain the
bridges of a decremental graph and we can also maintain the connected
components and their sizes without revealing what the current randomized
certificate looks like. All this is needed for the unique perfect matching
algorithm of Gabow, Kaplan, and Tarhan [GKT01]. The algorithm is an extremely
simple recursion based on the fact that a graph with a unique perfect matching
has a bridge and all components have even sizes. The algorithm first asks for
a bridge $(u,v)$ of some component. If there is none, the is no unique
matching. Otherwise we remove $(u,v)$ and check the sizes of the components of
$u$ and $v$. If they are odd, $(u,v)$ is in the unique matching, and we remove
all other incident edges. Otherwise $(u,v)$ is not in the unique matching. The
important thing here is that the bridges do not tell us anything about our
2-certificate of the 2-edge-connected components.

Thus we solve the static problem of deciding if a graph has a unique perfect
matching in $O(m)+\widetilde{O}(n)$ time. If the self-verification reports a
possible mistake, we simply rerun. Thus we get a Las Vegas algorithm that
terminates in $O(m)+\widetilde{O}(n)$ time with high probability.

###  1.4 Techniques

Our main technical contribution is a new construction of a sparse randomized
$c$-certificate that witnesses the $c$-edge-connected components of $G$ and
can be maintained under edge deletions in $G$. In the static case,
deterministic certificates of this kind have been known for decades [NI92].
However, they are not very robust in the decremental setting, where an
adversary can constantly remove its edges forcing it to update frequently.
Consequently, Thorup [Tho99] used a randomized sample-based certificate to
obtain his reduction. The general idea behind this approach is to ensure that
the certificate is sparse and undergoes few updates. Ideally, the sparse
certificate will only have to be updated whenever an edge from the certificate
is deleted. Using a fully dynamic data structure on the certificate, we may
obtain efficient algorithms provided that we don’t spend too much time on
maintaining the certificate. Thorup’s reduction had an additive overhead
$O(m\log(n^{2}/m))$ for maintaining the certificate, which we will reduce to
$O(m)$. We shall, in fact, use Thorup’s reduction as a subroutine, called on
$O(\log n)$ decremental subproblems each starting with $O(m/\log^{2}n)$ edges.

####  1.4.1 Thorup’s construction [Tho99]

Let us first briefly describe how Thorup’s algorithm operates on certificates
and highlight difficulties in improving his reduction to linear time. First of
all, the $c$-certificate is constructed as follows: initially, sample edges of
$G$ uniformly with probability $P\leq 1/2$, thus obtaining a subgraph $S$.
Then, compute the $c$-edge-connected components of $S$ and form a certificate
$H$ out of two parts: (1) A _recursive_ certificate of $S$, and (2) the
subgraph $D$ consisting of edges of $G$ connecting distinct $c$-edge-connected
components of $S$.

As proved by Karger [Kar99], $D$ has size $\widetilde{O}(cn/P)$ with high
probability. Thorup [Tho99] generalizes this by proving that $D$ undergoes
only $\widetilde{O}(cn/P)$ insertions throughout any sequence of edge
deletions to $S$. Since $D$ depends only on the $c$-edge-connected components
of $S$, it is enough to have a $c$-certificate of $S$ in order to define $D$.
Hence, a $c$-certificate of $S$ (which is a graph a size $O(mP)$, i.e., a
constant factor smaller) is maintained under edge deletions recursively. The
recursion stops when the size of the input graph is $O(cn)$. To maintain $D$
at each recursive level, we first need to maintain the $c$-edge-connected
components of the (recursive) certificate of $S$ under edge deletions. The
certificate of $S$ can be (inductively) seen to have $\widetilde{O}(cn/P)$
edges and undergo $\widetilde{O}(cn/P)$ updates. As a result, for $P=1/2$
maintaining its $c$-edge-connected components costs $\widetilde{O}(cn\cdot
T_{c}(n))$ total time using the fully-dynamic $c$-edge-cut data structure.
Since at each recursion level the certificate size decreases geometrically,
the expected cost of all the dynamic $c$-edge-cut data structures is
$\widetilde{O}(cn\cdot T_{c}(n))$.

The additional cost of $O(m\log(n^{2}/m))$ comes from the fact that, at each
level of the recursion, when a $c$-edge-connected component in $S$ splits into
two components as a result of an edge deletion, we need to find edges of $G$
between these two components in order to update $D$. This takes
$O(m\log{(n^{2}/m)})$ total time throughout using a standard technique of
iterating through the edges incident to the nodes in the smaller component
every time a split happens [ES81]. The $O(\log{(n^{2}/m)})$ (instead of
$O(\log{(n)})$) cost comes by noticing that a vertex can at most have $q$
neighbors in a component of order $q$, and that after we go through the edges
of a vertex $i$ times it is in a component of order $\leq n/2^{i}$; hence it
is only the first $O(\log(n/\deg(v)))$ times that all neighbors of $v$ have to
be considered, so the total time spent on this becomes $O\left(\sum_{v\in
V}\deg(v)\log(n/\deg(v))\right)=O(m\log{(n^{2}/m)})$.

It turns out very challenging to get rid of the $O(m\log(n^{2}/m))$ term
associated with finding cuts when components split in Thorup’s reduction. If
we knew that all of these cuts were _small_ , say of size at most $\delta$,
then we could apply a whole bag of tricks for efficiently finding them in a
total time of $\tilde{O}(n\delta)$, e.g., using invertible Bloom lookup tables
[GM11], or the XOR-trick [AGM12a, AGM12b, KKM13b]. Unfortunately, the bound of
$\tilde{O}(cn/P)$ only gives an average bound on the number of edges between
pairs of components, and in fact there can be pairs of components having as
many as $\Omega(n^{1/3})$ edges between them, as we will later show. In order
to resolve this, we have to introduce a new type of sample based $c$-edge
certificate obtained by only removing cuts of size at most
$\delta=O(c\operatorname{polylog}{n})$ from $G$. In the following three
subsections, we describe the ideas behind this new certificate, the technical
challenges encountered in efficiently maintaining it, and why such a
certificate is relevant for decremental connectivity algorithms.

####  1.4.2 A small cut sample certificate

On the highest level, our $c$-edge certificate of a graph $G=(V,E)$ is
constructed starting with a sample $S\subset G$. For now we assume that the
edges of $S$ are sampled independently with some probability $P\leq 1/2$, but
we will later see how to reduce the number of random bits needed for the
sampling to $O(\operatorname{polylog}{n})$. In our algorithms, $G$ will be the
current decremental graph and the sample $S$ will be made from the original
graph. Thus, when $G$ has undergone a sequence of deletions, the current
sample will be $S\cap G$. At any point in time, the maintained $c$-edge
certificate only depends on the sample $S$ and the current graph $G$, not on
the sequence of edge updates made to $G$ so far. We may therefore describe the
$c$-edge certificate statically.

The critical idea behind our certificate is to introduce a small-cut-parameter
$\delta$. Our certificate is obtained by iteratively removing certain cuts
from $G$ where each cut is allowed to be of size at most $\delta$. We denote
by $D\subset G$ the graph whose edge set consists of the edges removed in this
process. The overall goal is to define this cut removal process in a way so
that (1) each connected component of $G\setminus D$ is $c$-edge-connected in
$S$, and (2) it is easy to detect new small cuts under edge deletions issued
to $G$. We then use $S\cup D$ as our $c$-edge connectivity certificate of $G$.
Importantly, we want $\delta$ to be _as small as possible_ , ideally
$\delta=O(c\operatorname{polylog}(n))$. This is because $\tilde{O}(\delta n)$
will show up as an additive cost in our algorithm for maintaining the
certificate. We will describe shortly how this type of certificate can be used
in the design of efficient decremental $c$-edge-connectivity algorithms, but
let us first demonstrate that the existence of such a cut removal process for
a small $\delta$ is non-trivial.

First of all, we could simply remove _all_ cuts from $G$ of size at most
$\delta$ leaving us with the $(\delta+1)$-connected components. Karger’s
result [Kar99] implies that with $\delta=O((c+\log n)/P)$ sufficiently large,
these components will remain $c$-edge connected in $S$. However, in order to
maintain the small cuts, we would need a decremental $\delta$-edge
connectivity algorithm. As $\delta>c$, this approach simply reduces our
problem to a much harder one.

Suppose on the other hand that we attempted to use Thorup’s sampling
certificate [Tho99] described above. To simplify the exhibition, let’s assume
that $P=1/2$ and $c=1$. If $D$ is the set of edges between connected
components of $S$, $D\cup S$ is a certificate. Thorup’s algorithm recurses on
$S$ to find a final certificate of $G$. At first sight it may seem like $D$
can be constructed by iteratively removing cuts of size at most $\delta=O(\log
n)$ between the connected components of $S$. After all, isn’t it unlikely that
a connected component of $S$ has more than, say, $100\log n$ unsampled
outgoing edges when the sampling probability is $P=1/2$? As tempting as this
logic may be, it is flawed. To illustrate this, let $G=G(n,2/n)$ be the
Erdős–Rényi graph obtained by sampling each edge of the complete graph on $n$
vertices independently with probability $2/n$. Let further $S$ be the subgraph
of $G$ obtained by sampling each edge with probability $1/2$. Then $S$ is
distributed as the Erdős–Rényi graph $G(n,1/n)$ and basic phase transition
results [ER60] show that the two largest components of $S$, $C_{1}$ and
$C_{2}$, almost surely have size $\Theta(n^{2/3})$. Now, we can conversely
construct $G$ from $S$ by including each non-sampled edge of the complete
graph with probability $\frac{1}{n-1}$, and then we expect $G$ to contain as
many as $\Theta(n^{1/3})$ edges between $C_{1}$ and $C_{2}$. At some point in
the iterative process, we are thus forced to remove a cut of size
$\Omega(n^{1/3})$ splitting $C_{1}$ and $C_{2}$, and we would have to choose
$\delta$ of at least this size (but it is possible that other examples could
show that $\delta$ would have to be even larger). Our algorithms spend total
time $\tilde{O}(n\delta)$ on finding these cuts, and if
$\delta=\Omega(n^{1/3})$, this is not good enough for a linear time algorithm
for non-sparse graphs. We remark that in this example, each vertex of $G$ has
degree $O(\log n)$ with high probability. Therefore, an alternative approach
yielding cuts of size $O(\log n)$ would be to cut out one vertex at a time
moving all incident edges to $D$. In particular this would cut the large
sampled components $C_{1}$ and $C_{2}$ into singletons, one vertex at a time.
Clearly, we cannot proceed like this for general graphs which may have many
vertices of large degree. Nevertheless, this simple idea will be critically
used in our construction.

Our actual certificate uses $\delta=O(\frac{c\log n}{P})$. The certificate can
be constructed for any $P\leq 1/2$, but in our applications,
$P=1/\operatorname{polylog}{n}$. We proceed to sketch the construction now and
refer the reader to Section 4 for the precise details. On a high level, the
sample $S$ is partitioned into $\ell=O(\log n)$ samples
$S_{1},\dots,S_{\ell}$, each having size approximately $Pm/\ell$. To construct
our certificate, we start by iteratively pruning $G$ of the edges incident to
vertices of degree less than $\delta$, moving these edges to $D$. The graph
left after the pruning $G_{1}=G\setminus D$ satisfies that each vertex of
positive degree has degree at least $\delta$. Next, $S_{1}$ defines a sample
of $G_{1}$, $H_{1}=S_{1}\cap G_{1}$ and the bound on the minimum positive
degree in $G_{1}$ guarantees that with constant probability a fraction of
$3/4$ of the vertices with positive degree in the sampled subgraph $H_{1}$ has
degree $\geq 4c$ . We prove a combinatorial lemma stating that such a graph
can have at most $5n/6$ $c$-edge-connected components. As a result, if we
contract the $c$-edge-connected components of $H_{1}$ in the pruned graph
$G_{1}$, the resulting graph $G_{1}^{\prime}$ would have at most $5n/6$
vertices. Finally, we construct a $c$-certificate for $G_{1}^{\prime}$
recursively using the samples $S_{2},S_{3},\dots$, stopping when the
contracted graph has no edges between the contracted vertices (here $G$ played
the role of $G_{0}^{\prime}$). The constant factor decay in the number of
components ensures that we are done after $\ell=O(\log n)$ steps with high
probability. All edges of $D$ are obtained as the removed edges of cuts of $G$
of size less than $\delta$, so $D$ will have size $O(n\delta)$. Our
certificate will simply be $S\cup D$ which we prove is in fact a
$c$-certificate.

With this, we have thus completed the goal of obtaining a small cut sample
certificate with $\delta$ as small as $O(\frac{c\log n}{P})$. Abstractly, our
certificate has a quite simple description: we alternate between sampling,
removing small cuts around $c$-edge-connected components in the sample, and
finally contracting these components. However, in our implementation, we
cannot afford to perform the contractions as described above explicitly. This
makes it difficult to efficiently find the edges leaving the $c$-edge
connected components of $H$ (at a given recursive level), and we must be able
to do this since these $c$-edge-connected components may split as edges are
deleted from $G$. It turns out that since we are only concerned with cuts of
size at most $\delta$, we can in fact identify these cuts in total time
$O(m)+\tilde{O}(\delta n)$. We will describe this in the following section.

A final property of our new randomized decremental $c$-certificate algorithm
is that it requires only $O(\log^{2}n)$ random bits to yield high-probability
correctness bounds. This is in sharp contrast with Thorup’s algorithm [Tho99]
which requires $\Omega(m)$ random bits. On a high level, the reason we can do
with few random bits is that in each step of the construction of our
certificate, we only need the bounds on the number of contracted components to
hold with constant probability. Indeed, we will still only have $O(\log n)$
recursive levels with high probability. This means that for the probability
bounds within a single recursive level, it suffices to apply Chebyshev’s
inequality. While the reduction of the number of required random bits is nice,
the main point, however, is that with our new certificate we can get down to
constant amortized update time per edge-deletion for decremental
(2-edge)-connectivity for all but the sparsest graphs.

####  1.4.3 Maintaining our certificate

As edges are deleted from $G$, the recursive structure of the $c$-certificate
$H$ changes. Indeed, the deletion of an edge may cause the following changes
in one of the recursive layers of $H$: (1) introduce a cut of size less than
$\delta$ surrounding a $c$-edge-connected component or (2) break a $c$-edge-
connected component in two. In the first case, the edges of the cut have to be
moved to $D$, and deleted from the current and later layers of $H$, causing
further cascading. When a $c$-edge-connected component (in a recursive layer)
of $H$ breaks in two, we need to determine whether either of the new
components has less than $\delta$ outgoing edges in $G$. If we use the
standard technique of iterating over all the edges incident to nodes of the
smaller component, this again incurs an $O(\log(n^{2}/m))$ cost per edge which
is insufficient. However, as we only care about components with at most
$\delta$ outgoing edges, it turns out that we can do better. We define the
_boundary_ of a component $C$ of some graph $H\subset G$ to be the set of
edges of $G$ with one endpoint in $C$, and another in $V\setminus C$. To
overcome the $O(\log{(n^{2}/m)})$ cost per edge, we prove that we can maintain
boundaries of size at most $\delta$ under splits using a Monte Carlo
randomized algorithm in ${O(m+n\delta\operatorname{polylog}{n})}$ total time.
We realize this result by deploying the XOR-trick [AGM12a, AGM12b, KKM13b] in
a somehow unusual manner. In particular, we randomly partition the set of
edges of $G$ and use the XOR-trick to detect the parts that are relevant for
scanning, as opposed to standard applications of the XOR-trick, which are used
to detect a single replacement edge over a polylogarithmic number of
independent samples which unavoidably introduces a polylogarithmic dependence
in the cost per edge. Since we are not interested in discovering a single edge
incident to some set, we only need to apply the XOR-trick once, which allows
us to keep the running time linear in $m$.

####  1.4.4 Combining our certificate with Thorup’s algorithm

With the certificate as above, the overall idea for a decremental connectivity
algorithm is to maintain a $c$-certificate of (each recursive layer of) the
_decremental_ graph $H=S\setminus D$ using the algorithm by Thorup [Tho99]. By
choosing $P=1/\log^{2}n$, $S$ has $m^{\prime}=O(m/\log^{2}n)$ edges with high
probability, so employing the algorithm of Theorem 1.1 on each recursive layer
takes total time
$O(m^{\prime}\log^{2}n+ncT_{c}(n)\operatorname{polylog}{n})=O(m+ncT_{c}(n)\operatorname{polylog}{n})$
with high probability. Let $H^{*}$ be the $c$-certificate thus obtained for
$H$. Using a fully dynamic $c$-edge-connectivity algorithm on $H^{*}\cup D$
(which undergoes $O(cn\operatorname{polylog}{n})$ updates), we maintain a
$c$-edge certificate of $G$. As $H^{*}\cup D$ undergoes
$O(cn\operatorname{polylog}{n})$ updates, running the fully dynamic algorithm
takes total time $O(cnT_{c}(n)\operatorname{polylog}{n})$.

We remark that for $c=1,2$ we could instead use a fully dynamic $c$-edge
connectivity algorithm on $H$ with polylogaritmic update and query time at the
price of a smaller $P$ (which would incur more log-factors in our final time
bound). For $c>2$, however, we only know that
$T_{c}(n)=O(n^{1/2}\operatorname{poly}(c))$. Since, running a fully dynamic
algorithm on $H$ takes total time
$\Omega(mT_{c}(n)/\operatorname{polylog}{n})$, this is insufficient to obtain
linear time algorithms for dense graphs.

####  1.4.5 Final self-check

Let us finally describe the ideas behind the final self-checks claimed in
Theorem 1.2 and 1.3 in a more general context. In particular, we show that if
a randomized Monte Carlo dynamic algorithm satisfies some generic conditions
then it can be augmented to detect, at the end of its execution, whether there
is any chance that it answered any query incorrectly. That is, if the self-
check passes then it is guaranteed that all queries were answered correctly
throughout the execution of the algorithm. Otherwise, it indicates that some
queries might have been answered incorrectly. The self-check property is
particularly useful in applications of dynamic algorithms as subroutines in
algorithms solving static problems, that is, it enables static algorithms to
exhibit Las Vegas guarantees instead of the Monte Carlo guarantees provided by
the dynamic algorithm, as they can simply re-run the static algorithm with
fresh randomness until the self-check passes.

The properties of a dynamic algorithm amenable to a self-check behavior are as
follows:

  * •

Once a mistake is made by the dynamic algorithm it should be detectable and
any subsequent updates of the algorithm do not correct the mistake before it
is detected.

  * •

If the dynamic algorithm is stopped at any point in time, it should be able to
still perform the self-check within the guaranteed running time of the
algorithm.

In our algorithm, as long as the $c$-certificate maintained by our algorithm
is correct, the $c$-edge-connectivity queries answered by our algorithm
exhibit the same guarantees as the fully dynamic $c$-edge-connectivity
algorithm running on the $c$-certificate $H$. Hence, we only need to detect
potential mistakes in the process of maintaining the $c$-certificate $H$. Such
mistakes only happen with probability $n^{-\Omega(1)}$.

The $c$-certificate $H\subseteq G$ of $G$ that we maintain is such that it
includes every edge from $G$ that is not in a $c$-edge-connected component of
$G$ (more specifically, not in a $c$-edge-connected component of the
maintained sample $S\subset G$, which includes all edges not in $c$-edge-
connected components of $G$) and such that every $c$-edge-connected component
of $G$ is also a $c$-edge-connected component in $H$. A different equivalent
formulation is that for every edge $(u,v)$ of $G$, if $(u,v)$ is not in $H$,
then $u$ and $v$ are in the same $c$-edge-connected component of $H$.

As we later show, the only possible error in the maintenance of the
$c$-certificate is that an edge is missing from $H$ while its endpoints are
not $c$-edge-connected in $S$. Therefore, to satisfy the properties above, any
incorrectly missing edge in the $c$-certificate should remain missing until
the error is detected. We show (in the proof of Theorem 1.2) that before each
update to $H$ we can check whether the edge should have been part of the
certificate but was omitted due to an error. It is trivial to check for such
mistakes during the execution of our algorithm, as follows. For any edge that
is deleted from the graph we simply check whether the two endpoints of the
deleted edge belong to distinct $c$-edge-connected components of $H$ and, if
so, declare a potential error. For every edge that is inserted to the
certificate, due to the updates following an edge deletion, we check whether
the edge was supposed to be part of the certificate before the last edge
deletion but was omitted due to an error. In either case, our self-check flags
an execution invalid only if there has been a mistake (which might or might
not have affected $c$-edge-connectivity queries on the certificate), which
happens with low probability. As long as each vertex knows the ID of its
$c$-edge-connected component in the $c$-certificate, the aforementioned check
takes constant time to perform per edge deletion, and thus does not affect the
overall running time of our algorithm. Since our algorithm is Monte Carlo
randomized and we only flag an execution invalid if a mistake in the
maintenance of the certificate was detected, any single execution of our
algorithm is flagged invalid with probability $n^{-\Omega(1)}$.

Notice that if the algorithm is terminated before all edges are deleted, we
can simply iterate over the remaining edges and apply the aforementioned check
for each remaining edge.

##  2 Preliminaries

The problem of dynamic connectivity consists in designing a data structure
that maintains a dynamic undirected graph and supports two operations: an
_update_ operation which modifies the maintained graph, and a _query_
operation, which asks if two given vertices belong to the same connected
component of the current graph.

Dynamic connectivity comes in three variants, which differ in the allowed
types of update operations. The most general is the _fully dynamic_
connectivity problem, in which each update may either add or remove a single
edge. The two more restricted variants are _incremental_ connectivity – each
update adds a single edge, and _decremental_ connectivity – each update
removes a single edge.

##### Graphs.

Throughout the paper we consider undirected graphs which may have parallel
edges, but not self-loops. Generally, for $G=(V,E)$, we denote by $n$ and $m$
the number of vertices and edges of $G$, respectively. When referring to other
graphs $H=(V,E^{\prime})$, we write $|H|$ to denote $|E^{\prime}|$.

If $G^{\prime}=(V^{\prime},E^{\prime})$ is a graph with $V^{\prime}=V$ and
$E^{\prime}\subset E$ then $G^{\prime}$ is a _subgraph_ of $G$, denoted
$G^{\prime}\subseteq G$. If $W$ is a set of edges, then we denote by
$G\setminus W$ the graph with vertex set $V$ and edge set
$E^{\prime}=E\setminus W$. We often use $G\setminus H$ to denote $G\setminus
E(H)$. Finally, if $G=(V,E_{G})$ and $H=(V,E_{H})$ are graphs on the same set
of vertices, then $G\cup H$ is the graph with vertex set $V$ and edge set
$E_{G}\cup E_{H}$.

Let $A,B\subset V$ be subsets of vertices of $G=(V,E)$. The set of edges from
$A$ to $B$ in $G$ is denoted $E_{G}(A,B)$. For $A\subset V$, we denote by
$\partial_{G}(A)=E_{G}(A,V\setminus A)$ the _boundary_ of $A$ in $G$.

##### Cuts.

A _cut_ of $G=(V,E)$ is a partition of the vertices of $G$ into two non-empty
sets $V_{1},V_{2}$. We shall mostly identify the cut with the set of edges
crossing the cut, $E(V_{1},V_{2})$. The number of such edges is the _size_ of
the cut. A cut of $G$ of size $c\in\mathbb{N}$ is called a _$c$ -cut_ of $G$.
A _simple cut_ of $G$ is a set of edges $S\subset E$ such that $G\setminus S$
has exactly one connected component more than $G$ and such that for every
proper subset $S^{\prime}\subsetneq S$, $G\setminus S^{\prime}$ has the same
connected components as $G$.

##### Edge connectivity.

Let $c$ a be positive integer. Two distinct vertices $u,v$ of $G$ are _$c$
-edge-connected_ if there exist $c$ pairwise edge-disjoint paths from $u$ to
$v$. Being $c$-edge-connected is an equivalence relation on the vertices of
$G$ and we call the corresponding equivalence classes the _$c$ -edge-connected
classes_. The graph $G$ is _$c$ -edge-connected_ if it contains no cut of size
$<c$. Equivalently, a graph $G$ is $c$-edge-connected if every pair of
distinct vertices of $G$ are $c$-edge-connected. It is worth noting that the
graph consisting of a single vertex is $c$-edge-connected since it contains no
cut. The _$c$ -edge-connected components_ of $G$ are the maximal induced
$c$-edge-connected subgraphs of $G$, i.e., an induced subgraph $C$ of $G$ is a
$c$-edge-connected component if it is $c$-edge-connected and there exists no
intermediate subgraph $C\subsetneq C^{\prime}\subset G$ such that $C^{\prime}$
is $c$-edge-connected.

For $c=1$, we have simpler terminology. We say that 1-edge-connected vertices
are _connected_ and call the 1-edge-connected components of $G$ the _connected
components_ or simply _components_ of $G$. We also use $\mathcal{C}(G)$ to
denote the set of connected components of $G$.

##### Fully dynamic $c$-edge-cut.

The crucial ingredient in obtaining our general decremental algorithm for
arbitrary $c\geq 1$ is the _fully-dynamic $c$-edge-cut_ data structure,
defined as follows. Let $G$ be a graph. Then, the data structure maintains any
edge $e$ (if one exists) satisfying the following: $e$ belongs to some cut of
size $<c$ of the connected component of $G$ containing $e$. For each $c\geq
1$, we denote by $T_{c}(n)$ the amortized update time bound of such a data
structure that holds whp.

For example, for $c=1$ we have $T_{1}(n)=O(1)$ since we do not have to
maintain anything. For $c=2$, the data structure is required to maintain some
_bridge_ of $G$ and it is known that
$T_{2}(n)=O((\log{n}\cdot\log\log{n})^{2})$ [HRT18]. For $c\geq 3$, in turn,
we have $T_{c}(n)=O(n^{1/2}\operatorname{poly}{(c)})$ [Tho07].

##### Chernoff Bound.

In our analysis we will occasionally need the classic Chernoff concentration
bounds. We state a version here for convenience.

######  Theorem 2.1 (Chernoff Bound).

Let $X_{1},\dots,X_{n}$ be independent random variables supported on $[0,1]$
and denote by $\mu=\mathbb{E}\left[\sum_{i=1}^{n}X_{i}\right]$ the mean of
their sum. For every $\delta>0$,

$\displaystyle\forall\mu^{\prime}\geq\mu\colon\Pr\left[\sum_{i=1}^{n}X_{i}>(1+\delta)\mu^{\prime}\right]$
$\displaystyle\leq e^{-\frac{\mu^{\prime}\delta^{2}}{2+\delta}},\hskip
28.45274pt\forall\mu^{\prime}\leq\mu\colon\Pr\left[\sum_{i=1}^{n}X_{i}<(1-\delta)\mu^{\prime}\right]$
$\displaystyle\leq e^{-\frac{\mu^{\prime}\delta^{2}}{2}}.$

##### Uniform edge sampling.

Finally, for a graph $G=(V,E)$ and $p\in[0,1]$ a real number, we define the
_uniform edge sampling_ $G(p)$ as follows. Let $\\{X_{e}\\}_{e\in E}$ be
independent Bernoulli random variables with parameter $p$ and
$E^{\prime}=\\{e\in E\mid X_{e}=1\\}$. Then $G(p)=(V,E^{\prime})$.

##  3 Some Useful Properties of $c$-Edge-Connected Components

In this section, we present structural lemmas regarding the $c$-edge-connected
components, in particular in graphs where a significant fraction of the
vertices has degree at least $\Omega(c)$. As described in Section 1.4.2, at
each level of the recursive construction of our $c$-certificate, all $c$-edge-
connected components of the sampled graph are contracted into single vertices
in the recursive calls to the next levels. The following structural results
show that the number of vertices between subsequent levels shrink by a
constant factor, implying a $O(\log n)$ bound on the number of levels in our
certificate. We note that some proofs from Sections 3, 5.1, and 5 can be found
in Section 8.

######  Lemma 3.1 (Benczúr and Karger [BK15]).

Let $c$ and $n$ be positive integers. Every graph on $n$ vertices with
strictly more than $(c-1)(n-1)$ edges contains a non-trivial $c$-edge-
connected component.

######  Corollary 3.2.

Let $c$ be a positive integer and $G$ be a graph on $n$ vertices. Denote by
$q_{c}$ the number of $c$-edge-connected components of $G$. Then the number of
edges connecting distinct $c$-edge-connected components of $G$ is at most
$(c-1)(q_{c}-1)$.

Another central lemma is the following, stating that if a graph on $n$
vertices has at least $3/4n$ vertices with sufficiently high degree, the
number of $c$-edge-connected components is at most $5/6n$.

######  Lemma 3.3.

Let $G=(V,E)$ be a graph on $n$ vertices such that at least $3n/4$ of its
vertices have degree at least $4c$. The number of $c$-edge-connected
components of $G$ is at most $5n/6$.

###### Proof.

Denote by $q_{c}$ the number of $c$-edge-connected components of $G$. Let
$V_{0}\subset V$ be the set of vertices of $G$ that are trivial $c$-edge-
connected components. Then
$q_{c}\leq(n-|V_{0}|)/2+|V_{0}|=(n+\left|V_{0}\right|)/2$. Furthermore, every
edge incident to a vertex of $V_{0}$ connects distinct $c$-edge-connected
components of $G$. Since there are at most $n/4$ vertices with degrees less
than $4c$, at least $|V_{0}|-n/4$ vertices in $V_{0}$ have degree at least
$4c$. Hence, there are at least $2c\cdot(|V_{0}|-n/4)$ edges incident to
vertices in $V_{0}$. By Corollary 3.2, we have
$c\cdot(n+\left|V_{0}\right|)/2\geq 2c(\left|V_{0}\right|-n/4)$, which implies
$\left|V_{0}\right|\leq 2n/3$. The conclusion follows since
$q_{c}\leq(n+|V_{0}|)/2\leq 5n/6$. ∎

##  4 The new $c$-certificate

In this section we describe our new $c$-certificate that is instrumental in
obtaining the near-optimal decremental connectivity algorithm. A
$c$-certificate $H$ of a graph $G$ allows us to answer queries about $c$-edge-
connected components and $c$-edge-connected classes of $G$.

######  Definition 4.1 ($c$-certificate).

Let $G$ be a graph and $c\in\mathbb{N}$. A _$c$ -certificate_ for $G$ is a
subgraph $H\subseteq G$ such that the $c$-edge-connected components and
classes of $G$ are preserved in $H$.

Let $\delta>c$ and $\ell\geq 1$ be integers to be set later. The certificate
is defined based on $\ell+1$ levels of graphs $H_{i},G_{i}\subseteq G$ for
$i=0,\ldots,\ell$.

The first step is to sample graphs $H_{0}^{0},H_{1}^{0},\ldots,H_{\ell}^{0}$
that constitute the basis for graphs $H_{0},\ldots,H_{\ell}$. Let $p\in(0,1)$
be a real number to be fixed later. The sampled subgraphs satisfy
$(V,\emptyset)=H_{0}^{0}\subseteq H_{1}^{0}\subseteq\dots\subseteq
H_{\ell}^{0}$. Specifically, for each $i=1,\ldots,\ell$, $H_{i}^{\ell}$ is
constructed as follows. Let $s=\lceil pm\rceil$ and suppose
$E=\\{e_{1},\ldots,e_{m}\\}$. Let $r_{i}:\\{1,\ldots,s\\}\to\\{1,\ldots,m\\}$
be a _pairwise independent random number generator_ , or, in other words, a
pairwise independent hash function. Then, we set:

$H_{i}^{0}:=H_{i-1}^{0}\cup\left(V,\left\\{e_{r_{i}(1)},e_{r_{i}(2)},\ldots,e_{r_{i}(s)}\right\\}\right).$

However, we stress that for each level $i$, we require the random generator to
be fully independent from the random generators at previous levels
$1,\ldots,i-1$. It is well known [CW79] that a pairwise independent random
number generator can be implemented using $\Theta(\log{n})$ random bits so
that it generates numbers in constant time in the word RAM model. As a result,
if $\Theta(\ell\log{n})$ random bits are provided, each $H_{i}^{0}$ can be
constructed in $O(si)=O(mpi)$ time and has $O(mpi)$ edges.

Now, the graphs $H_{0},G_{0},H_{1},G_{1},\ldots,H_{\ell},G_{\ell}$ are defined
inductively. Set $G_{-1}=G$. Then for $i=0,\ldots,\ell$ the graphs
$H_{i},G_{i}$ are obtained as follows. First, the graph $H_{i}$ is obtained
from $H_{i}^{0}\cap G_{i-1}$ by repeatedly removing all the cuts of size less
than $c$. In other words, $H_{i}$ equals the $c$-edge-connected components of
$H_{i}^{0}\cap G_{i-1}$. Afterwards, the graph $G_{i}$ is in turn obtained
from $G_{i-1}$ as follows. While for some $c$-edge-connected component $C$ of
$H_{i}$, we have $|\partial_{G_{i}}(C)|<\delta$, the edges of the boundary
$\partial_{G_{i}}(C)$ are removed from both $H_{i}$ and $G_{i}$. Equivalently,
one could obtain $G_{i}$ by first contracting all the $c$-edge-connected
components of $H_{i}$ in the initial $G_{i}$, then repeatedly removing edges
incident to vertices of degree $<\delta$ in the contracted graph, and finally
undoing all the contractions.

By the construction, the graphs $H_{1},\ldots,H_{\ell}$ and
$G_{1},\ldots,G_{\ell}$ satisfy the following properties:

  1. (1)

Every connected component of $H_{i}$ is $c$-edge-connected.

  2. (2)

$H_{i}\subseteq G_{i}$ and $G_{i+1}\subseteq G_{i}$ for all $i\geq 0$.

  3. (3)

Each connected component $C$ of $H_{i}$ satisfies either
$\partial_{G_{i}}(C)=\emptyset$ or $|\partial_{G_{i}}(C)|\geq\delta$.

Moreover, we have the following property.

######  Lemma 4.2.

For any $i=0,\ldots,\ell-1$, $H_{i}\subseteq H_{i+1}$.

###### Proof.

First of all, note that $H_{i}\subseteq H_{i+1}^{0}\cap G_{i}$ since
$H_{i}\subseteq G_{i}$ and $H_{i}\subseteq H_{i}^{0}\subseteq H_{i+1}^{0}$.
Moreover, each component of $H_{i}$ is $c$-edge-connected so it is contained
in some $c$-edge-connected component of any supergraph of $H_{i}$, in
particular $H_{i+1}^{0}\cap G_{i}$. As a result, when obtaining $H_{i+1}$ from
$H_{i+1}^{0}\cap G_{i}$ by taking the $c$-edge-connected components, we never
remove edges of $H_{i}$. ∎

Figure 1 shows the inclusion relations between the graphs $G_{i},H_{i}$
(property (2) and Lemma 4.2).

${H_{\ell}}$${\subset}$${G_{\ell}}$${H_{\ell-1}}$${\subseteq}$${G_{\ell-1}}$${\vdots}$${\vdots}$${H_{1}}$${\subseteq}$${G_{1}}$${H_{0}}$${\subseteq}$${G_{0}}$${G}$

$\supseteq$$\subseteq$$\supseteq$$\subseteq$$\supseteq$$\subseteq$$\supseteq$$\subseteq$$\subseteq$

Figure 1: Illustration for Algorithm 1

######  Lemma 4.3.

There exists $\ell=O(\log{n})$ such that if $p\ell<1$ and $p\delta\geq 32c$,
then, with high probability, the connected components of $G_{\ell}$ are
$c$-edge-connected and equal to the connected components of $H_{\ell}$.

###### Proof.

Denote by $G_{i}^{\prime}$ the graph $G_{i}$ with the components of $H_{i}$
contracted. By property (3), every vertex in $G_{i}^{\prime}$ has degree
either 0 or at least $\delta$. Let $k_{i}$ be the number of positive (in fact,
at least $\delta$) degree vertices of $G_{i}^{\prime}$.

Recall that $H_{i+1}$ contains precisely the edges inside the $c$-edge-
connected components of ${H^{0}_{i+1}\cap G_{i}}$. Moreover, let
$H_{i+1}^{\prime}\subset G_{i}^{\prime}$ be the graph $H^{0}_{i+1}\cap G_{i}$
with the ($c$-edge-connected) components of $H_{i}$ contracted. Consider some
vertex $v^{\prime}$ of $G_{i}^{\prime}$. If $v^{\prime}$ has degree $0$ in
$G_{i}^{\prime}$ it does so as well in $H_{i+1}^{\prime}$. Otherwise, by
property (3), $v^{\prime}$ has degree at least $\delta$ in $G_{i}^{\prime}$.
Recall that the edges of $H^{0}_{i+1}\setminus H^{0}_{i}$ are chosen
independently of the graphs $G_{i}^{\prime}$ and $H_{i}$ (which only depend on
the randomness from levels $0,\ldots,i$) via sampling with replacement
$s=\lceil pm\rceil$ edges using a pairwise independent random number generator
$r_{i+1}$. Consider a random variable $X_{v^{\prime}}$ equal to the degree of
$v^{\prime}$ in $H_{i+1}^{\prime}$. We now prove that $v^{\prime}$ has degree
less than $4c$, i.e., $X_{v^{\prime}}<4c$ with probability no more than
$\frac{3}{16}$.

To this end, we introduce two more random variables
$Y_{v^{\prime}},Z_{v^{\prime}}$:

  * •

$Y_{v^{\prime}}$ equals the number of times an edge incident to $v^{\prime}$
is sampled when sampling $H_{i+1}^{0}\setminus H_{i}^{0}$:

$Y_{v^{\prime}}=\sum_{1\leq j\leq s}[e_{r_{i+1}(j)}\text{ is incident to
}v^{\prime}\text{ in }G_{i}^{\prime}]$

  * •

$Z_{v^{\prime}}$ equals the number of collisions incident to $v^{\prime}$
during sampling $H_{i+1}^{0}\setminus H_{i}^{0}$, i.e.,

$Z_{v^{\prime}}=\sum_{1\leq j<k\leq s}[r_{i+1}(j)=r_{i+1}(k)\text{ and
}e_{r_{i+1}(j)}\text{ is incident to }v^{\prime}\text{ in }G_{i}^{\prime}]$

Let $d=\deg_{G_{i}^{\prime}}(v^{\prime})\geq\delta$. Since $Y_{v^{\prime}}$ is
a sum of $s$ pairwise independent indicator variables with mean $d/m$, we
have:

$\displaystyle\mathbb{E}\left[Y_{v^{\prime}}\right]$ $\displaystyle=s\cdot
d/m=\lceil pm\rceil\cdot d/m\geq pd.$
$\displaystyle\text{Var}\left[Y_{v^{\prime}}\right]$
$\displaystyle=s\cdot(d/m)\cdot(1-d/m)\leq\lceil pm\rceil\cdot(d/m)\leq
2pm\cdot(d/m)=2pd.$

By $pd\geq p\delta\geq 32c\geq 32$ and Chebyshev’s inequality
$\Pr[Y_{v^{\prime}}\leq(1-\varepsilon)\mu]\leq\frac{\text{Var}\left[Y_{v^{\prime}}\right]}{\varepsilon^{2}(\mathbb{E}\left[Y_{v^{\prime}}\right])^{2}}$
we have:

$\Pr[Y_{v^{\prime}}\leq
pd/4]\leq\Pr[Y_{v^{\prime}}\leq\mathbb{E}\left[Y_{v^{\prime}}\right]/4]\leq\frac{2pd}{\frac{9}{16}(dp)^{2}}\leq\frac{32}{9pd}\leq\frac{1}{9}<\frac{1}{8}.$
(1)

By pairwise independence we also have:

$\mathbb{E}\left[Z_{v^{\prime}}\right]=\sum_{1<j<k\leq
s}\frac{1}{m}\cdot\frac{d}{m}\leq\frac{s^{2}}{2}\cdot\frac{d}{m^{2}}\leq\frac{4p^{2}m^{2}}{2}\cdot\frac{d}{m^{2}}=2p^{2}d.$

Since we are aiming at proving the lemma for $\ell=\gamma\cdot\log{n}$ for a
constant $\gamma$ of our choice, we can without loss of generality require
that $p\ell<1$ implies $p\leq 1/256$. Hence, using Markov’s inequality we
obtain:

$\Pr[Z_{v^{\prime}}\geq
pd/8]\leq\frac{\mathbb{E}\left[Z_{v^{\prime}}\right]}{pd/8}\leq
16p\leq\frac{1}{16}.$

Note that we have $X_{v^{\prime}}\geq Y_{v^{\prime}}-Z_{v^{\prime}}$. So,
$X_{v^{\prime}}\leq pd/8$ implies $Y_{v^{\prime}}-Z_{v^{\prime}}\leq pd/8$.
This in turn implies that either $Y_{v^{\prime}}\leq pd/4$ or
$Z_{v^{\prime}}\geq pd/8$. As a result, via the union bound we get:

$\Pr[X_{v^{\prime}}\leq pd/8]\leq\Pr[Y_{v^{\prime}}-Z_{v^{\prime}}\leq
pd/8]\leq\Pr[Y_{v^{\prime}}\leq pd/4]+\Pr[Z_{v^{\prime}}\geq
pd/8]\leq\frac{1}{8}+\frac{1}{16}=\frac{3}{16}.$

By $pd\geq 32c$ we have that $X_{v^{\prime}}<4c$ implies $X_{v^{\prime}}\leq
pd/8$, so we obtain $\Pr[X_{v^{\prime}}<4c]\leq\frac{3}{16}$ as desired.

Now let us consider the probability $q$ that more than a fraction of 1/4 of
such $n^{\prime}$ vertices $v^{\prime}$ (with degree at least $\delta$ in
$G_{i}^{\prime}$) have degree less than $4c$ in $H_{i+1}^{\prime}$. By (1),
the expected number of such vertices is clearly no more than
$\frac{3n^{\prime}}{16}$. As a result, by Markov’s inequality,
$q\leq\frac{3n^{\prime}}{16}\cdot\frac{4}{n^{\prime}}=\frac{3}{4}$. In other
words, with probability at least $1-q\geq 1/4$, at least a fraction of $3/4$
of positive-degree vertices $v^{\prime}$ of $G_{i}^{\prime}$ will have degree
at least $4c$ in $H_{i+1}^{\prime}$.

Observe that since $G_{i}\supseteq G_{i+1}\supseteq\ldots G_{\ell}\supseteq
H_{\ell}\supseteq\ldots\supseteq H_{i}$, the isolated vertices of
$G_{i}^{\prime}$ (which are obviously also isolated in $H_{i+1}^{\prime}$)
correspond to $c$-edge-connected components of $H_{i}$ that are also $c$-edge-
connected components of
$H_{i+1},H_{i+2},\ldots,H_{\ell},G_{i},\ldots,G_{\ell}$. Since $H_{i}\subseteq
H_{i+1}$, by Lemma 3.3, with probability at least $1/4$, the $k_{i}$ non-
isolated vertices of $G_{i}^{\prime}$ are “merged” into at most $5k_{i}/6$
$c$-edge-connected components of $H_{i+1}$. Observe that those are the only
$c$-edge-connected components of $H_{i+1}$ that can give rise to positive-
degree vertices of $G_{i+1}^{\prime}$. Consequently, with probability $\geq
1/4$ we have $k_{i+1}\leq 5k_{i}/6$. This proves that $k_{i}$ is very likely
to decrease geometrically with $i$. More concretely, the quantity $k_{i}$ is
$0$ for $i=\ell=z\cdot\log{n}$ (where $z$ is a sufficiently large constant)
with high probability via the Chernoff bound.

Note that the lemma follows by $k_{\ell}=0$, the fact that $H_{\ell}\subseteq
G_{\ell}$, and property (1) for $i=\ell$. ∎

Finally, we obtain a $c$-certificate by taking a union of $H_{\ell}$ and
$G\setminus G_{\ell}$. Roughly speaking, since $H_{\ell}$ sparsifies the
$c$-edge-connected components of $G_{\ell}$, replacing the subgraph $G_{\ell}$
with $H_{\ell}$ preserves both the $c$-edge-components and $c$-edge-classes.
The formal proof can be found in the Appendix.

######  Lemma 4.4.

Let $D:=G\setminus G_{\ell}$. $H_{\ell}\cup D$ constitutes a $c$-certificate
for $G$.

We now show that the basis of our construction, i.e., pairwise independent
sampling at $O(\log{n})$ levels, yields an interesting low-randomness
alternative to Karger’s result [Kar99] saying that if a graph $G$ is
$c^{\prime}$-edge-connected graph, where $c^{\prime}=\Omega((c+\log{n})/p)$,
then $G(p)$ is $c$-edge-connected with high probability (depending on the
constant hidden in the $\Omega$ notation). Roughly speaking, Karger’s proof
applies a Chernoff bound to an _exponential_ number of cuts in $G$ and
therefore requires sampling with full independence, i.e., $\Theta(m)$ random
bits. We show that the graph $H_{0}^{\ell}$ has a similar property, but
requires only _polylogarithmic_ number of random bits: pairwise independence
requires $O(\log{n})$ bits, and there are $O(\log{n})$ sampling levels.

######  Lemma 4.5.

Let $\ell=\Theta(\log{n})$ be as in Lemma 4.3. Let $p^{\prime}\in(0,1)$.
Suppose $G$ is $c^{\prime}$-edge-connected, where
$c^{\prime}=\Omega(c\log{n}/p^{\prime})$ and the constant hidden in the
$\Omega$ notation is sufficiently large. Then the sampled graph
$H_{\ell}^{0}$, defined as before, has $O(mp^{\prime})$ edges and is $c$-edge-
connected with high probability.

###### Proof.

By Lemma 4.3, if $p\ell<1$ and $p\delta\geq 12c$, then $H_{\ell}$ has the same
$c$-edge-connected components as $G_{\ell}$. In particular, for any
$c^{\prime}\geq c$, if $G_{\ell}$ is $c^{\prime}$-edge-connected, then
$H_{\ell}$ is $c$-edge-connected. Observe that $G_{\ell}$ can be obtained from
$G$ be repeatedly removing from $G$ some cuts of size less than $\delta$.
However, if $G$ is $c^{\prime}$-edge-connected for $c^{\prime}\geq\delta$, no
such cuts exist in $G$ so in fact we have $G=G_{\ell}$. Let
$p=p^{\prime}/\ell$, $\delta=12c/p=\Theta(c\log{n}/p^{\prime})$. It follows
that if $G$ is $\geq\delta$-edge-connected, i.e.,
$\Omega(c\log{n}/p^{\prime})$-edge-connected, then $H_{\ell}$ is $c$-edge-
connected with high probability. Since $H_{\ell}\subseteq H_{\ell}^{0}$, so is
$H_{\ell}^{0}$. ∎

##  5 Decremental Maintenance of a $c$-certificate

In this section we give an algorithm for maintaining a $c$-certificate of
Section 4 for a graph $G$ that is subject to edge deletions. Even though the
graph $G$ is decremental, our maintained certificate will undergo both edge
insertions and deletions. However, we will show that, for non-sparse graphs,
it is possible that the certificate undergoes only a sublinear-in-$m$ number
of updates throughout. Moreover, we will show that it is possible to maintain
the certificate in roughly $O(m)+{\widetilde{O}(c\cdot n\cdot T_{c}(n))}$ time
which is $O(m)$ for non-sparse graphs, depending on the known upper bounds on
$T_{c}(n)$.

In this section we disregard the total number of random bits needed to achieve
the claimed bounds. We discuss how the data structure can be implemented using
only $O(\operatorname{polylog}{n})$ random bits later in Section 7.

During initialization the algorithm samples $H_{0}^{0},\ldots,H_{\ell}^{0}$ as
described in Section 4 and initially sets $H_{i}:=H_{i}^{0}$ for all $i$.
Furthermore, at the start of the algorithm, each $G_{i}$ is (conceptually)
initialized to $G$. We stress at this point that the $\ell$ graphs $G_{i}$ are
stored explicitly only in the basic version of the algorithm. The refined
version avoids that, as will be discussed later on. The initialization of
graphs $H_{i}$ and $G_{i}$ – so that they match their definition from Section
4 – is completed using the update procedure as described below.

The update procedure simply rebuilds the subsequent levels $i=0,\ldots,\ell$
of the certificate according to their definition from Section 4. Each of these
maintained graphs $H_{i},G_{i}$ is decremental in time. A deletion of a single
edge $e$ of $G$ (or the final step of the initialization) may in general cause
a deletion of a larger set $A$ of edges from the level-$j$ graphs
$H_{j},G_{j}$. More precisely, $e$ is first deleted from $G_{0}$. This in turn
may give rise to new vertices of degree less than $\delta$ in $G_{0}$. Recall
that edges incident to such vertices should be repeatedly removed from $G_{0}$
until there are none; denote by $A$ the set of edges removed in this process
plus the edge $e$. Observe that all graphs at levels $1,\ldots,\ell$ are
subgraphs of $G_{0}$, so all the edges from $A$ should also be removed from
these graphs. More generally, if the level $j$ is passed a set $A$ of edges to
be removed, these edges are first removed from both $H_{j}$ and $G_{j}$. As a
result of this change, some new cuts of size less than $c$ may appear in
$H_{j}$, and consequently some $c$-edge-connected components of $H_{j}$ may
split. The splits (as well as the deletions of edges from $A$) may give rise
to new boundaries $\partial_{G_{j}}(C)$ of size less than $\delta$ that have
to be detected and pruned. The removed boundaries are added to the set $A$ to
be passed to subsequent levels.

Algorithm 1 summarizes this conceptual implementation of the above procedure
for rebuilding the certificate. In the algorithm, as well as in the following
we set $D:=G\setminus G_{\ell}$.

1

2

Input : A graph $G=(V,E)$, where $E=\\{e_{1},\ldots,e_{m}\\}$

Parameters : A real $p\in(0,1)$ and integers $\ell,\delta\in\mathbb{N}$

Maintains : A $c$-certificate of $G$ given by the graph $D\cup H_{\ell}$ as
defined below

3 Procedure  _Initialize(__)_ :

4 Initialize graphs $G_{0},\dots,G_{\ell}$ all equal to $G$;

5 Initialize the empty graph $D$;

6 $H_{0}\longleftarrow(V,\emptyset)$;

7 $s\longleftarrow\lceil pm\rceil$;

8 for  _$i=1$ to $\ell$_ do

9 $r_{i}\longleftarrow$ a 2-independent random number generator
$\\{1,\ldots,s\\}\to\\{1,\ldots,m\\}$;

10 $H_{i}\longleftarrow
H_{i-1}\cup(V,\\{e_{r_{i}(1)},e_{r_{i}(2)},\ldots,e_{r_{i}(s)}\\})$;

11

12 CleanUp(_$\emptyset$_);

13

14 Procedure  _Delete(_$e$_)_:

15 Delete $e$ from $G$ and $D$;

16 CleanUp(_$\\{e\\}$_);

17

18 /* Internal deletion of set of edges $A$, maintains $D$,
$\\{H_{j}\\}_{j=0}^{\ell}$ and $\\{G_{j}\\}_{j=0}^{\ell}$ */

19 Procedure  _CleanUp(_$A$_)_:

20 for  _$j=0$ to $\ell$_ do

21 Delete the edges of $A$ from $G_{j}$ and $H_{j}$;

22 while  _there exists an edge $g\in H_{j}$ contained in a cut of $H_{j}$ of
size $<c$_ do

23 Delete $g$ from $H_{j}$;

24

25 while  _there exists a component $C$ of $H_{j}$ with
$S:=\partial_{G_{j}}(C)$ satisfying $0<\left|S\right|<\delta$_ do

26 Add $S$ to $A$ and to $D$;

27 Delete $S$ from $G_{j}$;

28

29

30

31

Algorithm 1 Abstract algorithm for maintaining a $c$-certificate
decrementally.

The correctness of this approach follows by Lemmas 4.3 and 4.4 applied to each
subsequent version of the graph $G$. If the certificate is not revealed to the
user, and is only used to answer $c$-edge-connectivity queries or track
$c$-edge-connected components, randomness is not leaked as long as the
algorithm gives correct answers (which happens with high probability). By
suitably increasing the constants hidden in Lemma 4.3 we obtain high
probability correctness for _all_ the $O(m)$ versions of the graph.

In the following we assume that $\ell=\Theta(\log{n})$, $p=O(1/\log{n})$ and
$p\delta=\Omega(c)$ so that Lemma 4.3 implies that $H_{\ell}\cup D$ remains a
$c$-certificate for $G$.

######  Lemma 5.1.

The graph $H_{\ell}\cup D$ has initially $O(mp\log{n}+n\delta\log{n})$ edges
and undergoes $O(n\delta\log{n})$ edge insertions throughout.

###### Proof.

The bound on the initial size of $H_{\ell}$ follows easily by the used
sampling scheme. Moreover, $H_{\ell}$ is decremental, whereas the set $D$ can
undergo both insertions (when an edge is removed from $G_{\ell}$) and
deletions (when an edge deletion is issued to $G$). Therefore, we only need to
prove that $D$ undergoes $O(n\ell\delta)$ insertions throughout. To this end,
we show that each $G_{i}$ undergoes $O(n\delta)$ edge removals following a
detection of a component $C$ of $H_{i}$ with $0<|\partial_{G_{i}}(C)|<\delta$.
Recall that $H_{i}$ and $G_{i}$ are both decremental, so at most $2n-1$
different components can ever arise in $H_{i}$. Each such component causes at
most $\delta$ insertions to $D$ if its boundary size ever drops below
$\delta$. ∎

###  5.1 Supporting data structures

Now we define a few data structures that we use as subroutines when
maintaining the certificate. These results are either known or should be
considered folklore. For completeness, we provide the proofs of the lemmas in
this section in the Appendix.

##### Restricted fully-dynamic connectivity.

Suppose $G$ is a graph subject to edge insertions and deletions. However,
assume insertion of an edge $\\{u,v\\}$ is allowed only if $u$ and $v$ are
currently connected. As a result, the connected components of $G$ are
decremental in time in the sense that they can only split, but never merge. In
this restricted setting we can explicitly maintain the connected components of
each vertex and thus support constant-time connectivity queries.

######  Lemma 5.2.

Let $G$ be a graph subject to edge insertions and deletions. Suppose the
endpoints of each edge inserted are connected in $G$ immediately prior to the
insertion. Let $m$ be the number of initial edges in $G$ plus the number of
insertions issued. There is a data structure that maintains the connected
components $\mathcal{C}=\\{C_{1},\ldots,C_{k}\\}$ of $G$, and an explicit
mapping $q:V\to\\{1,\ldots,|\mathcal{C}|\\}$ such that $v\in C_{q(v)}$.
Moreover, after each edge deletion that increases the number of components of
$G$, the data structure outputs a pair $(j,A)$ describing how $\mathcal{C}$
evolves: the component $C_{j}$ is split into $C_{j}\setminus A$ and $A$, where
$|A|\leq|C_{j}\setminus A|$, and we set $C_{j}:=C_{j}\setminus A$ and
$C_{k+1}:=A$, and update $k\leftarrow k+1$. The total update time is
$O(m\log^{2}{n})$, whereas the sum of sizes of sets $A$ output is
$O(n\log{n})$.

##### Maintaining boundaries of splitting sets in a fully dynamic graph.

We will often need to solve the following abstract dynamic problem on graphs.
Suppose we have two possibly unrelated graphs: a _fully dynamic_ graph $G$ and
a _decremental_ graph $H$, both on $V$. We would like to maintain boundaries
$\partial_{G}(C)$ of all the connected components $C$ of $H$ under the allowed
updates to $G$ and $H$.

######  Lemma 5.3.

Let $G=(V,E)$ be a fully dynamic graph. Let $\mathcal{C}$ be the set of
connected components of some (possibly unrelated) decremental graph on $V$.
Suppose the updates to $\mathcal{C}$ are given in the same form as in the
output of the data structure of Lemma 5.2. Then, the boundaries
$\partial_{G}(C)$ for $C\in\mathcal{C}$ can be maintained explicitly subject
to edge insertions/deletions issued to $G$, and updates to $\mathcal{C}$ in
$O((n+m)\log{n})$ total time, where $m$ is the number of initial edges of $G$
plus the number of edge insertions issued to $G$.

###  5.2 Basic data structure

We now discuss how the algorithm maintaining the $c$-certificate can be
efficiently implemented. We start with a basic version of the data structure
that does not yet achieve linear dependence on $m$.

First consider maintaining the graphs $H_{i}$. Recall that we need to
efficiently detect cuts of size $<c$ in $H_{i}$ under deletions, prune $H_{i}$
of these cuts, and keep track of how the $c$-edge-connected components (or,
equivalently, the connected components) of $H_{i}$ evolve. To this end, we
will need the following auxiliary dynamic graph data structures. First of all,
we maintain a $c$-certificate of $H_{i}$ using the data structure of Theorem
1.1.444We could in principle use a _decremental_ $c$-edge-cut data structure
on the graph $H_{i}$ itself as opposed to a _fully dynamic_ data structure on
its $c$-certificate, but that would prove less efficient. On top of the
$c$-certificate of $H_{i}$, we set up a fully-dynamic $c$-edge-cut data
structure, and the data structure of Lemma 5.2. Since the $c$-edge-connected
components of $H_{i}$ are precisely the components of the graph obtained by
repeatedly removing $<c$-edge cuts from the $c$-certificate of $H_{i}$, these
components combined can maintain the $c$-edge-connected components of $H_{i}$
and provide an efficient description of the splits these components undergo.

In the basic version of our algorithm, for each $G_{i}$ in turn, we use a
separate decremental boundary maintenance data structure of Lemma 5.3, where
the connected components whose boundaries we care about come from $H_{i}$.
This data structure is passed all the updates to the components of $H_{i}$ as
described in Lemmas 5.2 and 5.3. Recall how the boundary maintenance
structures are used: while for some ($c$-edge-) connected component $C$ of
$H_{i}$, the boundary of $C$ in $G_{i}$ has positive size $<\delta$, we remove
that boundary from $G_{i}$ (and propagate that change to subsequent layers
$j>i$). In particular, for $i=0$, since $H_{0}$ is empty and has only trivial
components, this corresponds to removing from $G_{0}$ all edges incident to
vertices of degree $<\delta$ until no such vertices exist. The boundaries of
size less than $\delta$ can be accessed easily using the data structure of
Lemma 5.3 associated with $G_{i}$.

Assuming a fully-dynamic $c$-edge-cut data structure with amortized update
time $T_{c}(n)$ and a proper choice of parameters $p,\delta$, the above
algorithm runs in $\widetilde{O}(m)$ time and, most importantly, updates the
maintained $c$-certificate a sublinear (in $m$) number of times.

######  Lemma 5.4.

There exists a decremental algorithm maintaining a $c$-certificate for $G$
such that the certificate undergoes $O(nc\log^{4}{n})$ edge updates
throughout. The total update time of the algorithm is
$\widetilde{O}(m)+O(n(c+\log{n})\cdot T_{c}(n)\log^{3}{n})$ with high
probability.

###### Proof.

We set $p=\frac{1}{\log^{3}{n}}$. This forces us to set
$\delta=12c\log^{3}{n}$ for $p\delta$ to be sufficiently large which is
required by Lemma 4.3. Recall that each $H_{i}$ has $O(mp\ell)$ edges
initially and we maintain its $c$-certificate under edge deletions using
Theorem 1.1. As a result, this incurs a cost of
$O(mp\ell\log{n}+n\cdot(c+\log{n})\cdot T_{c}(n)\log^{2}{n})$ time. Since the
$c$-certificate of $H_{i}$ undergoes $O(n(c+\log{n}))$ updates, using a fully-
dynamic $c$-edge-cut data structure upon the maintained $c$-certificate of
$H_{i}$ costs ${O(n(c+\log{n})\cdot T_{c}(n))}$ time. Similarly, using the
data structure of Lemma 5.2 on the $c$-certificate of $H_{i}$ costs
$O(n(c\log{n})\log^{2}{n})$ time. Summing over all $\ell=O(\log{n})$ graphs
$H_{i}$, we get $O(mp\log^{3}{n}+n(c+\log{n})\cdot T_{c}(n)\log^{3}{n})$ time.
By our choice of $p$, the first term is $O(m)$.

We also use a simple-minded boundary maintenance data structure of Lemma 5.3
on each of $O(\log{n})$ graphs $G_{i}$ with components from $H_{i}$. The total
update time of these data structures is $O(m\log^{2}{n})$. The bound on the
number of updates to the certificate follows by Lemma 5.1. ∎

Note that the only obstacle preventing us from getting an $O(m)$ bound in
Lemma 5.4 is the maintenance of component boundaries for each pair
$(H_{i},G_{i})$ independently. The simple-minded solution yields an
$O(m\log^{2}{n})$ overhead for this task and in fact solves an overly general
problem of maintaining the boundaries regardless of their size: recall that we
only care about the precise elements of the set $\partial_{G_{i}}(C)$ for a
component $C$ of $H_{i}$ if $|\partial_{G_{i}}(C)|\leq\delta$. Otherwise, a
(high-probability) guarantee that $|\partial_{G_{i}}(C)|>\delta$ is sufficient
for our needs.

###  5.3 Maintaining small boundaries

We now describe how to obtain an $O(m)+\widetilde{O}(n\delta)$ bound for
maintaining all the required small boundaries. Note that this will imply the
desired $O(m)$ running time for sufficiently dense graphs, assuming $T_{c}(n)$
is low enough. First of all, let $\Delta_{i}:=G_{i}\setminus G_{\ell}$. We can
split the task of maintaining $\partial_{G_{i}}(C)$ into maintaining
$\partial_{G_{\ell}}(C)$ and $\partial_{\Delta_{i}}(C)$ separately. Clearly,
we have $\Delta_{i}\subset D$. Recall that $D$ (and thus also $\Delta_{i}$) is
initially empty and undergoes only $O(n\delta\log{n})$ insertions throughout.
As a result, we can afford maintaining the boundaries of the form
$\partial_{\Delta_{i}}(C)$ even exactly (i.e., regardless of their sizes)
using the data structure of Lemma 5.3 in $O(\ell\cdot
n\delta\log{n}\cdot\log{n})=O(n\delta\log^{3}{n})$ time.

It remains to show how to efficiently maintaining the boundaries
$\partial_{G_{\ell}}(C)$ for components $C$ of the graphs
$H_{1},\ldots,H_{\ell}$, provided that $|\partial_{G_{\ell}}(C)|\leq\delta$.
We accomplish this goal using three components.

##### The sampled graph $R$.

The first component is responsible solely for estimating the sizes
$|\partial_{G_{\ell}}(C)|$. Let $R$ be a graph obtained from $G_{\ell}$ via
uniform sampling with probability $q=1/\log^{2}{n}$. Clearly, the graph $R$
has size $\Theta(mq)$ with high probability by the Chernoff bound. Recall that
$G_{\ell}$ is decremental; whenever an edge $e$ of $G_{\ell}$ is deleted, it
is removed from $R$ as well if it was sampled. So $R$ can be initialized and
maintained in $O(m)$ total time. Assume
$\delta=\Omega(\log^{2}{n}\cdot\log{m})$, where the constant hidden is
sufficiently large. Then, for each version of $G_{\ell}$ in time, and each of
some $O(\operatorname{poly}\\{n,m\\})$ sets $C\subseteq V$ chosen
independently of $R$, $|\partial_{G_{\ell}}(C)|\leq\delta$ implies
$|\partial_{R}(C)|\leq 2q\delta$, and $|\partial_{R}(C)|\leq 2q\delta$ implies
$|\partial_{G_{\ell}}(C)|\leq 4\delta$, both with high probability via the
Chernoff bound.

##### The small-boundary oracle.

Consider the following abstract problem. Suppose $G=(V,E)$ is a fully-dynamic
graph. We would like to have a data structure that supports the following
query: given some $S\subseteq V$, compute $\partial_{G}(S)$. The obvious query
procedure would be to go through all edges incident to the vertices of $S$;
this would give a $O(|E(S,V)|)$ query bound. However, if
$|S|\cdot|\partial_{G}(S)|$ is significantly smaller than $|E(S,V)|$, a more
efficient solution is possible. Formally, we prove the following theorem which
we believe might be of independent interest.

######  Theorem 5.5.

Let $G=(V,E)$ be an initially empty graph subject to edge insertions and
deletions and let $s$, $1\leq s\leq n$, be an integral parameter. There exists
a data structure that can process up to $O(\operatorname{poly}{n})$ queries
about the current set $\partial_{G}(S)$, where $S\subseteq V$ is the query
parameter, so that with high probability, each query is answered correctly in
$O\left(|S|s+|E(S,V)|\cdot\frac{|\partial_{G}(S)|}{s}+\log{n}\right)$ time.
The data structure is initialized in $O(ns)$ time and can be updated in
constant time.

We use the above data structure for $G_{\ell}$ and only ask queries when
$|\partial_{G_{\ell}}(S)|=O(\delta)$. By setting $s=\delta\cdot\log^{2}{n}$ we
will achieve $O(|S|\delta\log^{2}{n}+|E(S,V)|/\log^{2}{n})$ query time. Since
$G_{\ell}$ undergoes $m$ updates, the total update time of this data structure
is $O(m+n\delta\log^{2}{n})$.

##### Maintaining small boundaries of $G_{\ell}$ under splits.

Finally, we show how to combine the above two components with a neat variant
of the data structure of Lemma 5.3 in order to maintain, for each $i$, the
boundaries of components $C$ of $H_{i}$ with
$|\partial_{G_{\ell}}(C)|\leq\delta$ in $\widetilde{O}(n\delta)+O(m/\log{n})$
time with high probability. Through all $i$, this will imply the desired
$\widetilde{O}(n\delta)+O(m)$ total time bound.

Let $\mathcal{C}=\\{C_{1},\ldots,C_{k}\\}$ be the components of $H_{i}$.
Recall that the data structure of Lemma 5.2 for the $c$-certificate of $H_{i}$
yields decremental updates of the form $(j,C^{\prime})$ (where $\emptyset\neq
C^{\prime}\subseteq C_{j}$ and $|C^{\prime}|\leq|C_{j}\setminus C^{\prime}|$)
to $\mathcal{C}$ that set $C_{j}:=C_{j}\setminus C^{\prime}$ and
$C_{k+1}:=C^{\prime}$. As argued in Lemma 5.2, the total number of updates is
at most $n-1$ and the sum of $|C^{\prime}|$ over all updates is $O(n\log{n})$.
We will show how to process these updates so that with high probability, at
all times for each $C_{j}$, $|\partial_{G_{\ell}}(C_{j})|\leq\delta$ implies
that we store the set $\partial_{G_{\ell}}(C_{j})$ explicitly. Wlog. assume
that $\mathcal{C}=\\{V\\}$ initially.

We will say that a set $S\subseteq V$ _has small boundary_ if
$|\partial_{R}(S)|\leq 2q\delta$. Otherwise, we say that $S$ _has large
boundary_. As argued before, with high probability, the subset of components
with small boundary includes all components $C$ or our interest, i.e., with
$|\partial_{G_{\ell}}(C)|\leq\delta$, and does not include any components with
$|\partial_{G_{\ell}}(C)|=\omega(\delta)$. We keep track of which components
have large/small boundaries by running a simple-minded boundary maintenance
data structure of Lemma 5.3 on $R$. The total update time of this data
structure is $O(n\log{n}+|R|\log{n})=O(n\log{n}+m/\log{n})$ whp.

A naive approach to solve our problem would be to maintain
$\partial_{G_{\ell}}(C)$ for small boundary components $C\in\mathcal{C}$.
However, this approach fails for the following reason. Suppose a component $C$
is split into $C^{\prime},C^{\prime\prime}$, where
$|C^{\prime}|\leq|C^{\prime\prime}|$. Assume that $C^{\prime\prime}$ does have
a small boundary, whereas $C$ and $C^{\prime}$ do not. It is then unclear how
to compute the set $\partial_{G_{\ell}}(C^{\prime\prime})$ (of size
$\leq\delta$) using time less than linear in either $|C^{\prime\prime}|$ or
$|E(C^{\prime},V)|$. Had $\Omega(n)$ splits like this happened, we could spend
time as much as either $\Theta(n^{2})$ or $\Theta(m\log{n})$ which is
obviously too much. We need a smarter approach.

First of all, denote by $\mathcal{S}$ be the family of sets $C$ that _ever_
appeared in $\mathcal{C}$ and had small boundary when still in $\mathcal{C}$.
We will maintain $\partial_{G_{\ell}}(S)$ for _all_ $S\in\mathcal{S}$ – as
opposed to exclusively for $S\in\mathcal{S}\cap\mathcal{C}$ as in the naive
approach. Moreover, for each $C\in\mathcal{C}$, $C\neq V$, we store (a pointer
to) $s(C)$: the unique smallest set in $\mathcal{S}$ such that $C\subsetneq
s(C)$. Initially we have $\mathcal{C}=\mathcal{S}=\\{V\\}$, and
$\partial_{G_{\ell}}(V)=\emptyset$.

We now show how to update the stored information when an update
$(j,C^{\prime})$ comes. Let $A=C^{\prime}$ and $B=C_{j}\setminus C^{\prime}$.
Recall that $|A|\leq|B|$. Then, if $C_{j}\in\mathcal{S}$, we have
$s(A)=s(B)=C_{j}$. Otherwise, we have $s(A)=s(B)=s(C_{j})$. Now, if some
$C\in\mathcal{C}$ becomes small-boundary555Recall that the boundaries
$\partial_{R}(C)$ are maintained explicitly using the simple-minded data
structure of Lemma 5.3. Consequently, it is easy to detect this event “on the
fly”. (either as a result of edge deletion issued to $R$ or immediately when
it appears), we compute $\partial_{G_{\ell}}(C)$ as follows. If
$|C|\leq|s(C)|/2$, then we compute $\partial_{G_{\ell}}(C)$ using the small
boundary oracle query on $C$. Otherwise, we compute it by issuing a query
about the set $s(C)\setminus C$ to the small boundary oracle and then taking
the symmetric difference
$\partial_{G_{\ell}}(s(C))\triangle\partial_{G_{\ell}}(s(C)\setminus C)$ which
equals $\partial_{G_{\ell}}(C)$. It is important to note that we do not
require that $s(C)\setminus C$ is an element of $\mathcal{S}$ here; it is
sufficient to have that $|\partial_{G_{\ell}}(s(C)\setminus C)|=O(\delta)$,
which follows by $\partial_{G_{\ell}}(s(C)\setminus
C)\subseteq\partial_{G_{\ell}}(C)\cup\partial_{G_{\ell}}(s(C))$ and
$|\partial_{G_{\ell}}(C)|,|\partial_{G_{\ell}}(s(C))|\leq\delta$ with high
probability. Clearly, taking the symmetric difference takes $O(\delta)$ time.

######  Lemma 5.6.

The total time spent on computing all the required boundaries
$\partial_{G_{\ell}}(C)$ for $C\in\mathcal{S}$ is
$O(n\delta\log^{3}{n}+m/\log{n})$ with high probability.

###### Proof.

Consider a natural tree that the sets of $\mathcal{S}$ form, where each $C\neq
V$ is a child of $s(C)$. Let
$\mathcal{S}^{*}=\\{C\in\mathcal{S}:|C|\leq|s(C)|/2\\}$. Computing boundaries
of sets $C\in\mathcal{S}$ such that $|C|\leq|s(C)|/2$, i.e., of sets
$C\in\mathcal{S}^{*}$, requires a single oracle query for
$\partial_{G_{\ell}}(C)$ per each $C\in\mathcal{S}^{*}$. By Theorem 5.5, such
a query costs

$O\left(|C|\delta\log^{2}{n}+\sum_{v\in
C}\frac{\deg(v)}{\log^{2}{n}}+\log{n}\right)$

time. When $|C|>|s(C)|/2$, $s(C)\setminus C$ equals the union of siblings of
$C$ in the tree that the sets of $\mathcal{S}$ form. So the cost of a query
for $\partial_{G_{\ell}}(s(C)\setminus C)$ is:

$O\left(\sum_{C^{\prime}\text{ a sibling of
C}}\left(|C^{\prime}|\delta\log^{2}{n}+\sum_{v\in
C^{\prime}}\frac{\deg(v)}{\log^{2}{n}}+\log{n}\right)\right)$

Observe that each $C^{\prime}\in\mathcal{S}$ has at most one sibling whose
size is at least $|s(C^{\prime})|/2$. As a result, each $C^{\prime}$ with
$|C^{\prime}|\leq|s(C^{\prime})|/2$ contributes to a sum above for at most one
$C\in\mathcal{S}$ with $|C|>|s(C)|/2$. As a result, the total time spent on
small boundary oracle queries (through all $C\in\mathcal{S}$) is:

$O\left(\sum_{C\in\mathcal{S}^{*}}\left(|C|\delta\log^{2}{n}+\sum_{v\in
C}\frac{\deg(v)}{\log^{2}{n}}\right)\right)=O\left(\sum_{v\in
V}\left(\delta\log^{2}{n}+\frac{\deg(v)}{\log^{2}{n}}\right)\cdot|\\{C\in\mathcal{S^{*}}:v\in
C\\}|\right).$

Observe that each $v\in V$ can be an element of at most $O(\log{n})$ sets of
$\mathcal{S}^{*}$: all these sets are ancestors of $\\{v\\}$ in the tree
corresponding to $\mathcal{S}$ and have size smaller than their respective
parent by a factor of at least $2$. As a result, the total time spent on this
step is $O(n\delta\log^{3}{n}+\sum_{v\in
V}\deg(v)/\log{n})=O(n\delta\log^{3}{n}+m/\log{n})$. This dominates the
$O(n\delta\log{n})$ cost of taking symmetric differences. ∎

We also need to maintain the stored boundaries $\partial_{G_{\ell}}(C)$ for
$C\in\mathcal{S}$ under edge deletions that $G_{\ell}$ undergoes. However, to
avoid spending $O(m)$ time per single $H_{i}$ on this, for this part we need
to consider all the graphs $H_{i}$ simultaneously. Note that for a fixed $i$,
$\mathcal{S}$ only grows and contains at most $2n-1$ elements. Hence, the
total size of the stored sets $\partial_{G_{\ell}}(C)$, $C\in\mathcal{S}$, is
$O(n\delta)$ (whp). For each $e\in E(G_{\ell})$ we maintain a list of pointers
to such stored boundaries with $e\in\partial_{G_{\ell}}(S)$, through all
$H_{i}$. The total number of pointers ever inserted into these lists is
clearly $O(n\delta\ell)=O(n\delta\log{n})$. When an edge $e$ is removed from
$G_{\ell}$, we scan the attached list of $e$ and remove this edge from the
required boundaries it was contained in. The total time spent on this can be
seen to be no more than the total number of insertions into the lists, i.e.,
$O(n\delta\log{n})$.

See 1.2

###### Proof.

Recall that the simple reduction from Lemma 5.4 had $O(m)+O(n(c+\log{n})\cdot
T_{c}(n)\log^{3}{n})$ operation cost of the fully-dynamic $c$-edge connected
components data structures. It also required setting $\delta$ to at least
$c\log^{3}{n}$. The cost of maintaining the needed small boundaries is
dominated by the application of Lemma 5.6 for each $i=1,\ldots,\ell$. The
statement about the running time of the algorithm follows.

We now turn to proving the statement that the algorithms offers a final self-
check after processing all updates. Notice that we only need to check that no
edge between distinct $c$-edge-connected components of the certificate was
missing at any point throughout the execution of the algorithm; indeed, even
if an edge with both endpoints in the same $c$-edge-connected component of the
certificate was missing that wouldn’t affect any answers to $c$-edge-
connectivity queries on the certificate.

First note that in a correct execution of our algorithm all edges between
distinct $c$-edge-connected components of $H_{l}$ (and hence, of the
certificate) are always present in the certificate. That is, we only need to
verify that no edge between two distinct ($c$-edge-) connected components of
$H_{l}$ is added and that each deleted edge from $G$ is either present in the
certificate or both of its endpoints belong to the same ($c$-edge-) connected
component of $H_{l}$. We assume that each vertex has access to the ID of its
($c$-edge-) connected component in $H_{l}$, so that we can check in constant
time whether the two vertices are part of the same ($c$-edge-) connected
component. These IDs are provided by invocation of the Lemma 5.2 on the
certificate. Whenever an edge $e$ is deleted from the graph $G$ (and hence
from the certificate), we simply check that $e$ is part of the certificate if
its endpoints are in distinct ($c$-edge-) connected components of $H_{l}$; if
that is not the case, we mark the execution of the algorithm invalid, as edge
$e$ should have been part of the certificate. On the other hand, if both the
endpoints of a deleted edge $e$ were part of the same ($c$-edge-) connected
component of $H_{l}$, then no query might have been answered incorrectly.

Finally, edges might be added to the certificate due to the update in our data
structures following an edge deletion from $G$. Again, we need to make sure
that no edge is added to the certificate that was supposed to be there before
the edge deletion and is omitted due to an error. Specifically, for the edges
added to the certificate we need to check that both of their endpoints are in
the same ($c$-edge-) connected component of $H_{l}$ right before the last edge
deletion from $G$ (which potentially caused the splitting of connected
components of $H_{l}$). If that is not the case, then we again flag the
execution invalid as the endpoints of these edges were part of distinct
($c$-edge-) connected components of $H_{l}$ and should already by part of the
certificate. Notice that the splits of ($c$-edge-) connected components of
$H_{l}$ are described by the output of the data structure of Lemma 5.2, and
hence the queries can be answered efficiently (even an $O(\log n)$ bound per
query would be enough to keep the running time withing the stated bound due to
the limited number of updates to the certificate). ∎

###  5.4 Small boundary oracle

In this section we prove Theorem 5.5. Recall that the goal is to have a data
structure that maintains a fully dynamic graph $G=(V,E)$ and supports queries
regarding $\partial_{G}(S)$, where $S\subseteq V$ is a query parameter.

First of all, we will leverage the well-known XOR trick [AGM12a, AGM12b] for
deciding if a boundary of some subset of vertices is non-empty. We now briefly
describe this method. Suppose each $e\in E$ is assigned a random bit-string
$x_{e}$ of length $\Theta(\log{n})$ that fits in $O(1)$ machine words. Let
$x_{v}=\bigoplus_{vw=e\in E}x_{e}$ denote the XOR of the respective bit-
strings of edges incident to $v$. Then, one can prove that, given $S\subseteq
V$, with high probability the XOR $\bigoplus_{u\in S}x_{u}$ is non-zero if and
only if $\partial_{G}(S)\neq\emptyset$. So, emptiness of $\partial_{G}(S)$ can
be tested in $O(|S|)$ time.

Let $s\geq 1$ be an integral parameter. The main idea is as follows. We
partition the edge set $E$ into $E_{1},\ldots,E_{s}$. Each $e\in E$ is
assigned to one of these sets uniformly at random. Let us apply the XOR-trick
for each $E_{i}$ separately. To this end, now $x_{v}$ is a vector of $s$ bit-
strings, where $x_{v}(i)=\bigoplus_{vw=e\in E_{i}}x_{e}$. Given that, in
$O(s|S|)$ time we can find the set $I$ of all $i$ such that
$\partial_{G}(S)\cap E_{i}\neq\emptyset$ (whp). Clearly, in order to find
$\partial_{G}(S)$, we only need to look for this boundary’s elements in
$\left(\bigcup_{i\in I}E_{i}\right)\cap E_{G}(S,V)$. If $|\partial_{G}(S)|$ is
small compared to $s$, one can prove that, with high probability, this
strategy is more efficient than iterating through the entire set $E(S,V)$. We
prove this formally below.

######  Lemma 5.7.

Let $S\subseteq V$. Then, with high probability, the query procedure computes
$\partial_{G}(S)$ correctly in
$O\left(s|S|+|E_{G}(S,V)|\cdot\frac{|\partial_{G}(S)|}{s}+\log{n}\right)$
time.

###### Proof.

Let the bit-strings $x_{e}$ consist of $\gamma=O(1)$ machine words, each with
at least $\lceil\log_{2}{n}\rceil$ bits. As argued before, computing the bit-
strings $y(i)=\bigoplus_{v\in S}x_{v}(i)$ for all $i=1,\ldots,s$ and finding
the set $I=\\{i:y(i)\neq 0\\}$ takes $O(s|S|)$ worst-case time.

Now, let us consider the number of edges searched. Suppose that $e\in
E_{G}(S,S)$ has endpoints $u,v\in S$ and belongs to $E_{j}$. Then $x_{e}$ does
not contribute to $y(j)$ as it is present twice in the XOR, once in $x_{v}(j)$
and once in $x_{u}(j)$. Hence, if $y(j)\neq 0$, i.e., $j\in I$, then there is
an edge of $E_{j}$ that has only one endpoint in $S$ and thus belongs to
$\partial_{G}(S)$. Since each $e\in\partial_{G}(S)$ contributes to a single
element of $y$, $\left|I\right|\leq\left|\partial_{G}(S)\right|$. Now, for
$e\in E$, let $Y_{e}$ be the indicator of the event $(e\in\bigcup_{i\in
I}E_{i})$, i.e., $Y_{e}=1$ if $e\in\bigcup_{i\in I}E_{i}$ and $Y_{e}=0$
otherwise. The set $I$ is entirely determined by the variables
$(x_{e})_{e\in\partial_{G}(S)}$, so for the remaining edges,
$E_{G}(S,V)\setminus\partial_{G}(S)=E_{G}(S,S)$, the random variables
$\\{Y_{e}\\}_{e\in E_{G}(S,S)}$ are mutually independent and independent of
the choice of $I$ except for its size, $\left|I\right|$. It follows that the
sum $Y=\sum_{e\in E_{G}(S,S)}Y_{e}$ satisfies

$\mathbb{E}\left[Y\right]=\left|E_{G}(S,S)\right|\cdot\frac{|I|}{s}\leq\left|E_{G}(S,V)\right|\cdot\frac{|\partial_{G}(S)|}{s}.$

Since $Y$ is a sum of independent random variables, we may write
$\mu=\left|E(S,V)\right|\cdot\left|\partial_{G}(S)\right|/s$. Let $t>0$ be a
constant and $\mu^{\prime}=\mu+3t\log{n}$, and apply the Chernoff bound of
Theorem 2.1 to get

$\displaystyle\Pr\left[Y>2\mu+6t\log(n)\right]=\Pr[Y>(1+1)\mu^{\prime}]\leq\exp(-\max\\{\mu,3t\log(n)\\}/3)\leq
n^{-t}.$

Thus, with high probability the number of edges checked by the algorithm is

$O\left(|\partial_{G}(S)|+|E_{G}(S,V)|\cdot\frac{|\partial_{G}(S)|}{s}+\log{n}\right),$

and, as a result, the running time of the query procedure is

$O\left(s|S|+|\partial_{G}(S)|+|E_{G}(S,V)|\cdot\frac{|\partial_{G}(S)|}{s}+\log{n}\right).$

To obtain the desired bound note that if $s\geq|\partial_{G}(S)|$, then the
term $|\partial_{G}(S)|$ above is dominated by $s|S|$, and otherwise it is
dominated by the third term.

Finally, let us consider the probability that the output of the query is
correct. It is not hard to see that the output is correct if and only if the
set $I$ corresponds to the set $J=\\{j\in[s]\mid
E_{j}\cap\partial_{G}(S)\neq\emptyset\\}$, since in that case, the algorithm
searches all groups containing an edge of $\partial_{G}(S)$. We have already
established that $I\subset J$. So let $j\in J$ be given. Then there is some
edge $e\in\partial_{G}(S)\cap E_{j}$. We have:

$\displaystyle y(j)=\bigoplus_{v\in
S}x_{v}(j)=\bigoplus_{f\in\partial_{G}(S)\cap E_{j}}x_{f}$

since for every edge $e$ of $E_{G}(S,S)$, $x_{e}$ appears twice in the XOR.
The probability that $y(j)=0$, or equivalently $j\not\in I$, is hence the
probability that $x_{e}=\bigoplus_{f\in(\partial_{G}(S)\setminus\\{e\\})\cap
E_{j}}x_{f}$. Since $x_{e}$ is independent of the right-hand side, this
probability is exactly $2^{|x_{e}|}\leq 2^{-\gamma\log_{2}{n}}\leq
n^{-\gamma}$. By a union bound, it follows that $J\subset I$ with probability
at least $1-\left|J\right|\cdot n^{-\gamma}\leq 1-sn^{\gamma}\leq
1-n^{\gamma-1}$. ∎

When an edge $e=uv$ is inserted into $G$, all we have to do is pick a random
set $E_{j}$ for $e$, sample a random bit-string $x_{e}$, and update
$x_{w}(j):=x_{w}(j)\oplus x_{e}$ for $w\in\\{u,v\\}$. To handle the deletion
of $e$, all we have to do is to repeat the last step of insertion and remove
$e$ from $E_{j}$. So an edge update can be clearly performed in
$O(\gamma)=O(1)$ worst-case time. The data structure can be initialized in
$O(ns+m)$ time by first filling the values $x_{v}(i)$ with zeros and then
inserting all the edges.

Finally, to guarantee high-probability correctness and query time bounds for
$\operatorname{poly}{(n)}$ queries, it is enough to set constants $\gamma$ and
$t$ (from the proof of Lemma 5.7) sufficiently large. The full pseudocode of
the data structure is given in Algorithm 2.

1

2

Input : A graph $G=(V,E)$ on $n$ vertices

Parameters : Positive integers $\gamma=O(1)$ and $s\leq n$.

3

4Procedure  _Initialize(__)_ :

5 Initialize $s$ sets $E_{1},\dots,E_{s}$;

6 Fill values $x_{v}(j)$ for $v\in V$ and $j\in[s]$ with all-zero bit-strings
of length $\gamma\cdot\lceil\log_{2}{n}\rceil$;

7 for  _$e\in E$_ do

8 Insert(_$e$_);

9

10

11 Procedure  _Insert(_$e=\\{u,v\\}$_)_:

12 Insert $e$ into some $E_{j}$ of $E_{1},\dots,E_{s}$ uniformly at random;

13 Let $x_{e}\in\\{0,1\\}^{\gamma\cdot\lceil\log_{2}{n}\rceil}$ be a bit-
string chosen uniformly at random;

14 Let $x_{v}(j):=x_{v}(j)\oplus x_{e}$;

15 Let $x_{u}(j):=x_{u}(j)\oplus x_{e}$;

16

17 Procedure  _Delete(_$e=\\{u,v\\}$_)_:

18 Let $E_{j}$ be the set containing $e$;

19 Delete $e$ from $E_{j}$;

20 Let $x_{v}(j):=x_{v}(j)\oplus x_{e}$;

21 Let $x_{u}(j):=x_{u}(j)\oplus x_{e}$;

22

23 Function  _FindBoundary(_$S$_)_: /* Find $\partial_{G}(S)$ for a subset
$S\subset V$ */

24 Let $B:=\emptyset$;

25 Let $y:=\bigoplus_{v\in S}x_{v}$;

26 Let $I:=\\{i\in[s]\mid y(i)\neq 0\\}$;

27 for  _$uv=e\in\bigcup_{i\in I}(E_{i}\cap E(S,V))$ with $u\in S$_ do

28 if  _$v\notin S$_ then $B:=B\cup\\{e\\}$ ;

29

30 return _B_

31

Algorithm 2 Small boundary oracle.

##  6 Decremental $c$-Edge-Connectivity

In this section we briefly explain how Theorem 1.2 implies decremental
$c$-edge-connectivity algorithms with $O(m)$ total update time for
sufficiently dense graphs.

It is important to note at this point that there are two settings that might
be of interest. First, we might want to have a decremental algorithm
maintaining $c$-edge-connected _components_ , that is, supporting queries
whether two vertices belong to the same $c$-edge-connected component of $G$.
However, we might alternatively want to have a decremental algorithm
maintaining the $c$-edge-connected _classes_ , i.e., supporting queries
whether there exist $c$ edge-disjoint paths between some two vertices. Recall
that these settings are equivalent for $c=1,2$, but differ for $c\geq 3$: then
a pair of $c$-edge-connected vertices might not belong to the same $c$-edge-
connected component.

Let us first consider the decremental $c$-edge-connected components problem.
Then we have:

######  Theorem 6.1.

There exists a Monte Carlo randomized decremental $c$-edge-connected
components algorithm with $O(m+nc(\log^{7}{n}+\log^{4}{n}\cdot T_{c}(n)))$
total update time. The algorithm is correct with high probability.

###### Proof.

We maintain a $c$-certificate $H$ of $G$ using Theorem 1.2. Observe that $H$
has the same $c$-edge-connected components as $G$. We additionally maintain a
fully-dynamic $c$-edge-cut data structure for $H$, and a data structure of
Lemma 5.2. These two combined allow us to prune the certificate from
$<c$-edge-cuts and explicitly maintain the $c$-edge-connected components of
$H$ (which enables constant-time queries about the component a vertex belongs
to). Since $H$ undergoes only $O(nc\log^{4}{n})$ edge updates, and each can be
processed in $O(T_{c}(n)+\log^{2}{n})$ amortized time, the theorem follows. ∎

By plugging in the specific known upper bounds on $T_{c}(n)$ for $c=1,2$, we
obtain:

See 1.4

For $c\geq 3$, $T_{c}(n)=O(n^{1/2}\operatorname{poly}{(c)})$ has been proved
[Tho07], and therefore for $c=O(n^{o(1)})$ the $c$-edge-connected components
can be maintained under deletions in $O(m)+\widetilde{O}(n^{3/2+o(1)})$ total
time. See 1.6

Now consider the decremental $c$-edge-connected classes problem., i.e.,
decremental pairwise $c$-edge-connectivity.

######  Theorem 6.2.

Suppose there exists a fully-dynamic $c$-edge-cut algorithm with $T_{c}(n)$
amortized update time, and a fully-dynamic pairwise $c$-edge-connectivity
algorithm with $U_{c}(n)$ amortized update time and $Q_{c}(n)$ query time.
There exists a Monte Carlo randomized decremental $c$-edge-connected
components algorithm with
$O(m+nc\log^{7}{n}+n(c+\log{n})T_{c}(n)\log^{2}{n}+nc\log^{4}{n}\cdot
U_{c}(n))$ total update time and $O(Q_{c}(n))$ query time. The algorithm is
correct with high probability.

###### Proof.

We maintain a $c$-certificate $H$ of $G$ using Theorem 1.2. Recall that $H$
has the same $c$-edge-connected components as $G$. So, we additionally
maintain the certificate using the assumed fully-dynamic $c$-edge-connected
classes data structure and use it to answer queries. ∎

Jin and Sun [JS20] have recently showed that for $c=(\log{n})^{o(1)}$, a
deterministic fully-dynamic $c$-edge-connected classes data structure with
$U_{c}(n)=O(n^{o(1)})$ and $Q_{c}(n)=O(n^{o(1)})$ exists. By combining their
result with the fully-dynamic $c$-edge-cut algorithm of Thorup [Tho07] with
${T_{c}(n)=O(n^{1/2}\operatorname{poly}{(c)})}$, we obtain the following.

See 1.5

##  7 Reducing the Number of Random Bits

In this section we show that our algorithms can be tuned to require only
$O(c\operatorname{poly}\log n)$ random bits over all updates. We take
advantage of the pseudorandom number generator by Christiani and Pagh [CP14],
which, given only a $O(c\operatorname{poly}\log n)$ truly random bits, can
generate $O(n)$ random numbers, such that each number is between $1$ and
$n^{\prime}$, $n\leq n^{\prime}\leq 2n$ and the generated numbers are
$\Theta(c\operatorname{poly}\log n)$-independent. Generating each number takes
$O(1)$ time, whereas initialization takes $O(c\operatorname{polylog}{n})$
time.

The key property that we use is the fact that $\Theta(\log n)$-independence is
sufficient for a Chernoff-like bounds to hold [CP14].

Our algorithm uses randomness for three purposes:

  1. 1.

In order to initially sample the graphs $H_{i}^{0}$ (for all $i$) and $R$.

  2. 2.

Within the data structure of Theorem 1.1 to maintain a $c$-certificate of each
$H_{i}$.

  3. 3.

Within the small-boundary oracle, to partition the edges of $E$ into sets
$E_{1},\ldots,E_{s}$ .

  4. 4.

Within the small-boundary oracle, to generate the random bits associated with
each edge.

We now discuss how to implement each item using the pseudorandom generator of
[CP14].

We already argued in Section 4 that for sampling
$H_{1}^{0},\ldots,H_{\ell}^{0}$, a polylogarithmic number of random bits is
sufficient. For the sampled graph $R$ we only used Chernoff bounds for a
polynomial number of sums of indicator variables, so indeed polylogarithmic
independence is enough, and the sampling can be performed using the
pseudorandom generator of [CP14].

When making use of the partition in item (3), for efficiency we only apply the
Chernoff bound to a polynomial number of sums of independent indicator
variables $Y_{e}$ with the same mean for edges $e$ in some subset of $E$.
Hence, $O(\operatorname{polylog}{n})$-independence between the variables
$Y_{e}$ is sufficient. The partition of $E$ can be performed by sampling each
$E_{i}$ to be a $\left\lceil(m-\sum_{j<i}|E_{j}|)/(s-i+1)\right\rceil$-subset
of $E\setminus\left(\bigcup_{j<i}E_{j}\right)$. This is easily implemented
using the pseudorandom generator.

Consider item (4). Whenever the decremental certificate algorithm performs a
query on the small boundary oracle, with high probability the requested
boundary $\partial_{G}(S)$ contains $O(c\cdot\operatorname{polylog}{n})$
edges. As a result, only $O(c\cdot\operatorname{polylog}{n})$ edge bit-strings
$x_{f}$ participate in each computed value
$y(j)=\bigoplus_{f\in\partial_{G}(S)\cap E_{j}}x_{f}$. Therefore, it is enough
that the edge bit-strings are $O(c\operatorname{polylog}{n})$ independent
instead of fully independent.666In general, the XOR trick can be used with
polylogarithmic independence even for testing non-emptiness of large (i.e., up
to size $n$) boundaries [GKKT15, Tho18]. Although a single bit of an edge bit-
string can be generated in constant time [Tho18], we need $\Theta(\log{n})$
bits per edge to guarantee high probability correctness. As a result, using
known tools, generating all edge bit-strings would cost $\Theta(m\log{n})$
time which is too expensive for our application. As a result, the individual
bit-strings can be obtained from the pseudorandom generator in $O(m)$ time.

Finally, dealing with item (2) is less straightforward. This is because in the
analysis of the data structure of [Tho99, Theorem 6], Thorup invokes a result
due to Karger [Kar99] saying that if a graph $G$ is $c^{\prime}$-edge-
connected graph, where $c^{\prime}=\Omega((c+\log{n})/p^{\prime})$, and
$p^{\prime}\in(0,1)$ then $G(p^{\prime})$ is $c$-edge-connected with high
probability (depending on the constant hidden in the $\Omega$ notation). This
is then used to show that the number of edges between different $c$-edge-
connected components of a certificate (which is $G(p^{\prime})$ augmented with
the edges of $G$ connecting distinct $c$-edge-connected components of $G(p)$ ,
where $p^{\prime}$ is any constant less than $1$) that Thorup uses is
$O(c^{\prime}n)$ with high probability. This is where the $c+\log{n}$ term in
the bounds in Theorem 1.1 comes from. Unfortunately, roughly speaking,
Karger’s proof applies a Chernoff bound to an _exponential_ number of cuts in
$G$ and therefore requires sampling with full independence, i.e., $\Theta(m)$
random bits.

We can eliminate the need for full independence in [Tho99], albeit at the cost
of replacing the $c+\log{n}$ terms in the bounds of Theorem 1.1 with
$c\log{n}$. To this end, one can leverage Lemma 4.5 and replace the uniformly
sampled subgraph $G(p^{\prime})$ with the graph $H_{\ell}^{0}$ from our
construction with $p$ set to $p^{\prime}/\ell$ (computable in
$O(mp\ell)=O(mp^{\prime})$ time using $O(\operatorname{polylog}{n})$ random
bits), at the cost of replacing the $c+\log{n}$ terms with $c\log{n}$ in the
bounds of Theorem 1.1.

##  8 Omitted Proofs

See 3.1

###### Proof.

We proceed by strong induction on $n$. The statement is clearly true for
$n=1,2$. Consider now a graph $G$ on $n>2$ vertices and $(c-1)(n-1)+1$ edges.
If no simple cut of $G$ of size $d<c$ exists, then $G$ is $c$-edge-connected
and we are done. Otherwise, deleting the simple cut from $G$, we obtain
subgraphs $G_{1}$ and $G_{2}$ of $G$ of sizes $n_{1}$ and $n_{2}$,
respectively, such that $n_{1}+n_{2}=n$. After deleting the simple cut there
are at least $(c-1)(n-2)+1=(c-1)(n_{1}-1)+(c-1)(n_{2}-1)+1$ edges left. Hence,
by the pigeonhole principle and the induction hypothesis, either $G_{1}$ or
$G_{2}$ contains a non-trivial $c$-edge-connected component. ∎

See 3.2

###### Proof.

Contracting the $c$-edge-connected components of $G$ we arrive at a graph
$G^{\prime}$ on $q_{c}$ vertices with no $c$-edge-connected components. All
edges of $G$ that connect distinct $c$-edge-connected components of $G$ are
still present in $G^{\prime}$. By Lemma 3.1, $G^{\prime}$ contains at most
${(c-1)(q_{c}-1)}$ edges, which completes the proof. ∎

See 5.2

###### Proof.

First of all, we store $G$ in a fully-dynamic connectivity data structure with
$O(\log^{2}{n})$ amortized update time and $O(\log{n})$ query time [HdLT01].
This data structure also maintains a spanning forest explicitly and allows
$O(\log{n})$-time queries about the size of the component containing a given
vertex. If an edge is inserted, we just pass the insertion to the fully-
dynamic data structure – this insertion does not change the connected
components of $G$. If an edge $\\{u,v\\}$ is deleted, we additionally check if
$u$ and $v$ are still connected after removing $\\{u,v\\}$. If not, assume
wlog. that the component of $u$ is not smaller than that of $v$ afterwards. We
set $A$ to be the vertices of the tree containing $v$ in the spanning forest.
Let $q(u)=C_{j}$. For each $x\in A$ we remove $x$ from $C_{j}$, and set
$q(x):=k+1$. Finally, we set $C_{k+1}:=A$, increment $k$, and output $(j,A)$.
To bound the total time spent outside the fully-dynamic connectivity data
structure, note that each time we spend time proportional to the size of the
output set $A$. Whenever a vertex $x$ belongs to $A$, the size of the
component of $x$ decreases by a factor of at least two due to the edge update.
As a result, each $x$ can occur $O(\log{n})$ times in the output sets $A$, and
hence the total size of these sets is $O(n\log{n})$. ∎

See 5.3

###### Proof.

Note that similarly as in Lemma 5.2, the updates to $\mathcal{C}$ are given in
such a way that we can explicitly maintain, for each $v\in V$, the component
from $\mathcal{C}$ it belongs to. This takes $O(n\log{n})$ total time. It also
enables us to decide in $O(1)$ time whether an edge $\\{u,v\\}$ belongs to two
(if $u,v$ are disconnected) or zero boundaries (otherwise). Each boundary
$\partial_{G}(C)$ is stored in a linked list $L(C)$. Each edge of $G$
connecting endpoints in different components of $\mathcal{C}$ has associated
two pointers to its places in the two respective lists. Hence, whenever an
edge is inserted/deleted from $G$, the lists storing the boundaries can be
easily updated in constant time.

Now suppose $\mathcal{C}$ is updated: some $C_{j}\in\mathcal{C}$ gets split
into $C_{j}\setminus A$ and $A$, where $|A|\leq|C_{j}\setminus A|$. Clearly,
only the lists $L(C_{j})$ and $L(A)$ may need to be fixed at this point. We
now iterate through all $\\{u,v\\}=e\in E_{G}(A,V)$ and proceed as follows.
Suppose wlog. that $u\in A$. If $v\in C_{j}\setminus A$, then we add $e$ to
$L(C_{j})$ (it was not there before the split) and update all the auxiliary
pointers. Otherwise, if $v\in V\setminus(C_{j}\cup A)$, then $e$ is removed
from $L(C_{j})$ and inserted into $L(A)$. Otherwise, if $v\in A$, then we skip
that edge as it remains an intra-component edge after the split. It is easy to
verify that the lists represent the required boundaries after this step, which
takes $O\left(\sum_{u\in A}\deg(u)\right)$ time.

Finally, the $O(m\log{n})$ total update time bound follows since the incident
edges of each vertex $v$ are traversed $O(\log{n})$ times – when this happens,
the size of $v$’s component in $\mathcal{C}$ halves. ∎

See 4.4

###### Proof.

First, we prove that $H_{\ell}\cup D$ preserves the $c$-edge-connected
components of $G$. For convenience, denote $G_{c}=H_{\ell}\cup D$. Assume, by
contradiction, this is not true. Note that for each $c$-edge-connected
component $C^{\prime}$ of $H_{\ell}$ it holds that $C^{\prime}\subset C$ for
some $c$-edge-connected $C$ component of $G$, as otherwise $G[C^{\prime}]$
contains a $<c$-cut and so does $H_{\ell}[C^{\prime}]$ since $H_{\ell}\subset
G$; a contradiction. Let $C$ be a $c$-edge-connected component of $G$ that is
not preserved in $G_{c}$. Then, there exists a $k$-cut $S$, for $k<c$, in
$G_{c}[C]$ that is not a $k$-cut in $G[C]$. Let $C_{1},C_{2}$ be the two
different connected components of $G_{c}[C]\setminus S$. To conclude the
argument, we next show that all edges in $(C_{1}\times C_{2})\cap E$ are
present in $G_{c}$, which implies that if $S$ is a $k$-cut in $G_{c}[C]$ it is
also a $k$-cut in $G[C]$, and hence we contradict the assumption that $C$ is a
$c$-edge-connected component in $G[C]$ but not in $G_{c}[C]$. Take any edge in
$uv\in(C_{1}\times C_{2})\cap E$. Vertices $u$ and $v$ belong to different
$c$-edge-connected components of $H_{\ell}$, as otherwise, there would be no
$k$-cut separating $u,v$ in $G_{c}$ which contains $H_{\ell}$. Hence, the edge
$uv\in D\subseteq G_{c}$, since $D$ contains all edges of $G$ between
components of $H_{\ell}$. This concludes the proof that $G_{c}$ preserves the
$c$-edge-connected components of $G$.

Now we turn to proving that $G_{c}$ preserves also the $c$-edge-connected
classes of $G$. To this end, we first show that every $<c$-cut of $G_{c}$ is a
$<c$-cut of $G$. Let $S$ be a $<c$-cut of $G_{c}$. For contradiction, suppose
some $u,v\in V$ are connected in $G\setminus S$ but not in $G_{c}\setminus S$.
Let $P$ be a $u\to v$ path in $G\setminus S$. The endpoints of some edge
$xy\in P$ have to be disconnected in $G_{c}\setminus S$, as otherwise a path
from $u$ to $v$ would exist in $G_{c}\setminus S$. However, if $xy$ is
contained in $G_{\ell}$, then $x$ and $y$ lie in the same $c$-edge-connected
component of $H_{\ell}$, i.e., they are connected in $H_{\ell}\setminus S$ by
$|S|<c$. Otherwise, since $D=G\setminus G_{\ell}$, we have $xy\in D\setminus
S$, so $x$ and $y$ are connected in $G_{c}\setminus S$ as well. This
contradicts the fact that $x$ and $y$ are disconnected in $G_{c}\setminus S$.

Now, let $u,v\in V$. If $u$ and $v$ are $c$-edge-connected in a subgraph of
$G$, in particular $G_{c}$, then they are $c$-edge-connected in $G$.
Conversely, if $u$ and $v$ are not $c$-edge-connected in $G_{c}$ then there is
a cut of size $<c$ separating them in $G_{c}$. Such a cut is also a cut in $G$
by the previous claim, so $u$ and $v$ are not $c$-edge-connected in $G$
either. This proves that the $c$-edge-connected classes of $G$ and $G_{c}$ are
identical. ∎

## References

  * [AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459–467. SIAM, 2012.
  * [AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 5–14. ACM, 2012.
  * [AHR98] S. Alstrup, T. Husfeldt, and T. Rauhe.  Marked ancestor problems.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 534–543, 1998.
  * [ASS97] Stephen Alstrup, Jens Peter Secher, and Maz Spork.  Optimal on-line decremental connectivity in trees.  Information Processing Letters, 64(4):161 – 164, 1997.
  * [BK15] András A. Benczúr and David R. Karger.  Randomized approximation schemes for cuts and flows in capacitated graphs.  SIAM Journal on Computing, 44(2):290–319, 2015.
  * [CGL+19] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  CoRR, abs/1910.08025, 2019.
  * [CP14] Tobias Christiani and Rasmus Pagh.  Generating k-independent variables in constant time.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 196–205. IEEE Computer Society, 2014.
  * [CW79] Larry Carter and Mark N. Wegman.  Universal classes of hash functions.  J. Comput. Syst. Sci., 18(2):143–154, 1979.
  * [EGIN97] David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig.  Sparsification - a technique for speeding up dynamic graph algorithms.  J. ACM, 44(5):669–696, 1997.
  * [ER60] Paul Erdos and Alfred Renyi.  On the evolution of random graphs.  Publ. Math. Inst. Hungary. Acad. Sci., 5:17–61, 1960.
  * [ES81] Shimon Even and Yossi Shiloach.  An on-line edge-deletion problem.  J. ACM, 28(1):1–4, 1981.
  * [Fre85] Greg N. Frederickson.  Data structures for on-line updating of minimum spanning trees, with applications.  SIAM J. Comput., 14(4):781–798, 1985.
  * [FS89] M. Fredman and M. Saks.  The cell probe complexity of dynamic data structures.  In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (STOC), STOC ’89, page 345–354, New York, NY, USA, 1989\. Association for Computing Machinery.
  * [FT87] Michael L. Fredman and Robert Endre Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  J. ACM, 34(3):596–615, 1987.
  * [GI93] Zvi Galil and Giuseppe F. Italiano.  Maintaining the 3-edge-connected components of a graph on-line.  SIAM J. Comput., 22(1):11–28, 1993.
  * [GI96] Dora Giammarresi and Giuseppe F. Italiano.  Decremental 2- and 3-connectivity on planar graphs.  Algorithmica, 16(3):263–287, 1996.
  * [GKKT15] David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn.  Dynamic graph connectivity with improved worst case update time and sublinear space.  CoRR, abs/1509.06464, 2015.
  * [GKT01] Harold N. Gabow, Haim Kaplan, and Robert Endre Tarjan.  Unique maximum matching algorithms.  J. Algorithms, 40(2):159–183, 2001.
  * [GM11] Michael T Goodrich and Michael Mitzenmacher.  Invertible bloom lookup tables.  In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 792–799. IEEE, 2011.
  * [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  J. ACM, 48(4):723–760, July 2001.
  * [HHKP17] Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie.  Fully dynamic connectivity in _O_(log _n_(log log _n_)${}^{\mbox{2}}$) amortized expected time.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 510–520, 2017.
  * [HK99] Monika Rauch Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  J. ACM, 46(4):502–516, 1999.
  * [HR18] Jacob Holm and Eva Rotenberg.  Good r-divisions imply optimal amortised decremental biconnectivity.  CoRR, abs/1808.02568, 2018.
  * [HRT18] Jacob Holm, Eva Rotenberg, and Mikkel Thorup.  Dynamic bridge-finding in _Õ_(log${}^{\mbox{2}}$ _n_) amortized time.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 35–52, 2018.
  * [JS20] Wenyu Jin and Xiaorui Sun.  Fully dynamic c-edge connectivity in subpolynomial time.  CoRR, abs/2004.07650, 2020.
  * [Kar99] David R. Karger.  Random sampling in cut, flow, and network design problems.  Math. Oper. Res., 24(2):383–413, 1999.
  * [KKM13a] Bruce M. Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131–1142, 2013.
  * [KKM13b] Bruce M. Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, page 1131–1142, USA, 2013. Society for Industrial and Applied Mathematics.
  * [KKPT16] Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup.  Faster worst case deterministic dynamic connectivity.  In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 53:1–53:15, 2016.
  * [LS17] Jakub Lacki and Piotr Sankowski.  Optimal decremental connectivity in planar graphs.  Theory Comput. Syst., 61(4):1037–1053, 2017.
  * [NI92] Hiroshi Nagamochi and Toshihide Ibaraki.  A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph.  Algorithmica, 7(5&6):583–596, 1992.
  * [NSW17] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 950–961, 2017.
  * [PD04] Mihai Pǎtraşcu and Erik D. Demaine.  Lower bounds for dynamic connectivity.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 546–553, New York, NY, USA, 2004. Association for Computing Machinery.
  * [PT11] Mihai Pǎtraşcu and Mikkel Thorup.  Don’t rush into a union: take time to find your roots.  In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 559–568, 2011\.
  * [Tar75] Robert Endre Tarjan.  Efficiency of a good but not linear set union algorithm.  J. ACM, 22(2):215–225, April 1975.
  * [Tho99] Mikkel Thorup.  Decremental dynamic connectivity.  Journal of Algorithms, 33(2):229 – 243, 1999.
  * [Tho00] Mikkel Thorup.  Near-optimal fully-dynamic graph connectivity.  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 343–350, 2000\.
  * [Tho07] Mikkel Thorup.  Fully-dynamic min-cut.  Comb., 27(1):91–127, 2007.
  * [Tho18] Mikkel Thorup.  Sample(x)=(a*x<=t) is a distinguisher with probability 1/8.  SIAM J. Comput., 47(6):2510–2526, 2018.
  * [Wan15] Zhengyu Wang.  An improved randomized data structure for dynamic graph connectivity.  CoRR, abs/1510.04590, 2015.
  * [Wul13] Christian Wulff-Nilsen.  Faster deterministic fully-dynamic graph connectivity.  In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757–1769. SIAM, 2013.