# Fully Dynamic Exact Edge Connectivity in Sublinear Time

Gramoz Goranci Institute for Theoretical Studies, ETH Zurich. This project is
supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. Part of this work was done while the author was at the University
of Glasgow. email<EMAIL_ADDRESS>Monika Henzinger Faculty of
Computer Science, University of Vienna. See funding information in the
acknowledgement section. email<EMAIL_ADDRESS>Danupon
Nanongkai Max Planck Institute for Informatics & University of Copenhagen &
KTH. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme under grant agreement No 715672. Nanongkai was also partially
supported by the Swedish Research Council (Reg. No. 2019-05622). email:
<EMAIL_ADDRESS>Thatchaphol Saranurak University of Michigan. This
project is supported by NSF CAREER grant 2238138. email<EMAIL_ADDRESS>Mikkel
Thorup University of Copenhagen. This project is supported by Investigator
Grant 16582, Basic Algorithms Research Copenhagen (BARC), from the VILLUM
Foundation. email<EMAIL_ADDRESS>Christian Wulff-Nilsen University
of Copenhagen. This project is supported by the Starting Grant 7027-00050B
from the Independent Research Fund Denmark under the Sapere Aude research
career programme. email<EMAIL_ADDRESS>
###### Abstract

Given a simple $n$-vertex, $m$-edge graph $G$ undergoing edge insertions and
deletions, we give two new fully dynamic algorithms for exactly maintaining
the edge connectivity of $G$ in $\tilde{O}(n)$ worst-case update time and
$\tilde{O}(m^{1-1/16})$ amortized update time, respectively. Prior to our
work, all dynamic edge connectivity algorithms assumed bounded edge
connectivity, guaranteed approximate solutions, or were restricted to edge
insertions only. Our results answer in the affirmative an open question posed
by Thorup [Combinatorica’07].

##  1 Introduction

The edge connectivity of an undirected, unweighted graph $G=(V,E)$ is the
minimum number of edges whose removal disconnects the graph $G$. Finding the
edge connectivity of a graph is one of the cornerstone problems in
combinatorial optimization and dates back to the work of Gomory and Hu [23] in
1961. Since then, a large body of research work has dealt with the question of
obtaining faster algorithms for this problem in the classical sequential
setting [12, 45, 26, 15, 55, 37, 36, 38, 27, 42, 6, 16, 44, 17, 41]. This line
of work culminated in a breakthrough result by Kawarabayashi and Thorup [38]
in 2015 who obtained a _deterministic_ algorithm that runs in
$\tilde{O}(m)$111We use $\tilde{O}(\cdot)$ to hide poly-logarithmic factors.
time on a $n$-vertex, $m$-edge graph, which was later improved by Henzinger,
Rao, and Wang [27] to $O(m\log^{2}n\log\log^{2}n)$. Edge connectivity has also
been extensively studied in various models of computation including the
parallel model [34, 18, 43], the distributed models [51, 19, 49, 20, 10, 50,
21, 22, 11], the semi-streaming model [1, 44, 4], and several query models
[52, 44, 40]. All these models admit non-trivial, if not near-optimal,
algorithms for _exactly_ computing edge connectivity.

We study edge connectivity in the _fully dynamic_ setting, where the
underlying graph $G$ undergoes edge insertions and deletions, known as edge
_updates_ , and the goal is to maintain the edge connectivity of $G$ after
each update with as small update time as possible. In contrast to the long
line of research work in other computational models, the only known algorithm
for the fully dynamic edge connectivity problem is the trivial solution of
recomputing the edge connectivity from scratch after each update, which costs
$\tilde{\Theta}(m)$ time per update. Thorup [56] introduced this problem and
gave a fully dynamic edge connectivity algorithm that supports fast updates as
long as the edge connecitvity is upper bounded by some parameter $\eta$, where
$\eta$ is a small polynomial in $n$. Concretely, his algorithm achieves
$\tilde{O}(\eta^{7}\sqrt{n})$ worst-case time per edge update, and thus is
slower than the trivial algorithm whenever
$\eta=\tilde{\Omega}(m^{\nicefrac{{1}}{{7}}}n^{-\nicefrac{{1}}{{14}}})$. In
spite of dynamic graph algorithms being a flourishing research field, prior to
our work, there has been no progress on the fully dynamic edge connectivity
problem in the last 15 years.

In this paper we give the first solutions with $o(m)$ update time, answering
in the affirmative an open question posed by Thorup [56] of whether this is
possible. More concretely, we show the following two results.

###### Theorem 1.1

Given an undirected, unweighted $n$-vertex, $m$-edge graph $G=(V,E)$, there is
a fully dynamic randomized algorithm that processes an online sequence of edge
insertions or deletions and maintains the edge connectivity of $G$ in
$\tilde{O}(n)$ worst-case update time with high probability.

The above randomized algorithm works against an _adaptive_ adversary and
achieves _sub-linear_ update time as long as $m=\Omega(n^{1+\epsilon})$ where
$\epsilon$ where is some positive constant. We complement both points of this
result by designing a second algorithm that is (i) deterministic and (ii)
achieves sub-linear update times regardless of graph density.

###### Theorem 1.2

Given an undirected, unweighted $n$-vertex, $m$-edge graph $G=(V,E)$, there is
a fully dynamic _deterministic_ algorithm that processes an online sequence of
edge insertions or deletions and maintains the edge connectivity of $G$ in
$\tilde{O}(m^{\nicefrac{{7}}{{8}}}n^{\nicefrac{{1}}{{16}}})=\tilde{O}(m^{1-\nicefrac{{1}}{{16}}})$
amortized update time.

Both algorithms can also report the edges on a cut that attains the edge
connectivity of $G$ in time nearly proportional to the edge connectivity, with
the caveat that the algorithm from Theorem 1.1 then only works against an
_oblivious_ adversary.

###  1.1 Our Techniques

In this section, we discuss the main obstacles that explain the lack of
progress on fully dynamic exact edge connectivity algorithms and point out the
key ideas that enable us to achieve our results.

Before 2015, all near-linear time algorithms for exact edge connectivity
reduced to computing a minimum 2-respecting cut of a spanning tree [36]. This
problem involves setting up a sophisticated dynamic programming solution, and
the question of whether this solution admits fast dynamic algorithms remains a
notoriously hard open problem. For the somewhat easier problem of maintaining
a minimum 1-respecting cut of a spanning tree [13, 3, 56], state-of-the-art
dynamic algorithms allow us to solve the problem efficiently. In fact, this is
used as a key subroutine in Thorup’s algorithm [56] that
$(1+\epsilon)$-approximates edge connectivity in $\tilde{O}(\sqrt{n})$ worst-
case update time.

In a breakthrough work, Kawarabayashi and Thorup [38] in 2015 showed a largely
different approach to tackling the edge connectivity problem. Their key
insight was to introduce a notion of sparsification for edge connectivity in a
subtle way: given an undirected, unweighted $n$-vertex $G$, one can contract
edges of $G$ and obtain a graph $G^{\prime}$ such that (i) $G^{\prime}$ has
only $O(n)$ edges and (ii) $G^{\prime}$ preserves all _non-singleton_ minimum
cuts of $G$.222A non-singleton minimum cut is a minimum cut where both sides
of the cut contain at least $2$ vertices. Throughout, we call the graph
$G^{\prime}$ a _non-singleton minimum cut sparsifier_ (abbrv. _NMC
sparsifier_). Since maintaining singleton minimum cuts boils down to
maintaining the minimum degree of $G$, and the latter can be easily achieved
as $G$ undergoes edge updates, we can focus our attention to designing fully
dynamic algorithms for maintaing the NMC sparsifier $G^{\prime}$.

In the insertions-only setting, Goranci, Henzinger, and Thorup [24] observed
that an NMC sparsifier interacts well with edge insertions, as it satisfies a
certain composability property. Specifically, they showed that given an NMC
sparsifier $G^{\prime}$ of a graph $G$ and an edge insertion $e$ to $G$, the
graph $G^{\prime}\cup\\{e\\}$ remains an NMC sparsifier of $G\cup\\{e\\}$.
This was in turn combined with Henzinger’s insertions-only algorithm [29] for
maintaining small edge connectivity and $k$-connectivity certificates.
Periodically invoking a static algorithm for computing NMC sparsifier in a
black-box manner then led to a dynamic algorithm with poly-logarithmic
amortized update time per edge insertion.

We may be tempted to employ the same approach for handling edge deletions.
However, a short afterthought reveals that the crucial composability property
we used for edge insertions completely fails for edge deletions. This suggests
that restricting to edge deletions does not seem to help in the dynamic NMC
sparsifier problem, so in this work we refocus our attention to the fully
dynamic setting.

We devise two new fully dynamic NMC sparsifier algorithms which lead us to
Theorems 1.1 and 1.2, respectively. The first one is randomized and is based
on a dynamic variant of the random $2$-out contraction technique leveraged by
Ghaffari, Nowicki, and Thorup [22] (§3), whereas the second one is
deterministic and builds upon the expander decomposition-based approach for
computing edge connectivity by Saranurak [53] (§4). We note that the original
construction of NMC sparsifiers [38] is already quite involved in the static
setting and seems difficult to adapt in the dynamic setting. In the paragraphs
below, we give a succinct summary of the technical ideas behind both of our
algorithms.

Key to our randomized algorithm for dynamically maintaining an NMC sparsifier
is the following construction: given a graph $G$, for each vertex $u\in V$,
sample two incident edges to $u$ independently, with replacement, and contract
them to obtain the graph $G^{\prime}$, which we call a _random $2$-out
contraction_ of $G$. Despite the fact that $G^{\prime}$ is known to have only
$O(n/\delta)$ vertices [22], where $\delta$ is the minimum degree of $G$, the
number of edges in $G^{\prime}$ could potentially still be large, say
$\omega(n)$, and thus inefficient for our purposes. The main technical
component of our dynamic algorithm is to efficiently maintain a _sparse_
$\delta$-connectivity certificate $H^{\prime}$ of $G^{\prime}$. Towards
achieving this goal, we have to deploy a variety of algorithmic tools from
sequential, parallel, and streaming algorithms, namely (i) sequential and
parallel constructions of $k$-connectivity certificates [46, 10], and (ii)
constructing spanning forests in sub-linear time using linear
$\ell_{0}$-sampling sketches [9, 33]. A more detailed description of the
algorithm can be found in §3.

Our deterministic algorithm follows the now-widespread and powerful
algorithmic approach of employing _expander decompositions_ for solving graph-
based optimization problems. At a high level, an expander decomposition is a
partitioning of a graph into _well-connected_ clusters, whose expansion is
controlled by a parameter $\phi\in(0,1)$, such that there are few inter-
cluster edges left, say roughly $\phi m$. If $\phi\approx\delta^{-1}$, then
Saranurak [53] recently showed that contracting a carefully chosen _vertex
subset_ of each expander in the decomposition leads to a NMC sparsifier
$G^{\prime}$. Our main technical contribution is a simple, deletions-only
algorithm for maintaining an expander decomposition (based on expander
prunning [54]), which in turn leads to a deletions-only algorithm for
maintaining the NMC sparsifier $G^{\prime}$. While expander pruning has been
already used for dynamically maintaining other graph-based properties [25, 5],
we believe that our construction is one of the simplest and may prove useful
in future applications. We extend our deletions-only NMC algorithm to a fully
dynamic one by keeping edge insertions “on the side” and rebuilding
periodically. Finally, for achieving our claimed sub-linear update time, our
NMC sparsifier algorithm is run in “parallel” with the exact fully dynamic
edge connectivity algorithm of [56] which returns correct answers only for
small edge connectivity. For further details we point the reader to §4.

###  1.2 Related Work

The study of _approximation_ algorithms for the fully dynamic edge
connectivity problem was initiated by Karger [35] who gave a randomized
algorithm that maintains a $\sqrt{1+2/\varepsilon}$ to edge connectivity in
$\tilde{O}(n^{1/2+\varepsilon})$ expected amortized time per edge operation.
Karger and Thorup [57] showed a fully dynamic algorithm that
$(2+\epsilon)$-approximates edge connectivity in $\tilde{O}(1)$ amortized
updated time. Thorup [56] improved the approximation factor to $(1+\epsilon)$
at the cost of increasing the update time to $\tilde{O}(\sqrt{n})$. However,
his running time guarantees are worst-case instead of amortized.

Prior to our work, all known fully dynamic algorithms for _exactly_ computing
the edge connectivity $\lambda(G)$ of $G$ take sub-linear time only when
$\lambda(G)$ is small. In the same work [56], Thorup also showed an exact
fully dynamic algorithm with $\tilde{O}(\lambda(G)^{7}\sqrt{n})$ worst-case
update time, which is sub-linear whenever
$\lambda(G)=o(m^{1/7}n^{-1/14})$.333Nevertheless, Thorup’s result does not
assume that $G$ is an undirected, unweighted graph. For $\lambda(G)$ being a
small constant, edge connectivity can be maintained in $\tilde{O}(1)$
amortized update time. Specifically, there were a series of refinements in the
literature for designing fully dynamic algorithms for graph connectivity
(i.e., checking whether $\lambda(G)\geq 1$) [13, 28, 31, 33, 48, 7] and
$2$-edge connectivity (i.e., checking whether $\lambda(G)\geq 2$) [14, 30, 31,
32]. When the underlying dynamic graph is guaranteed to remain _planar_
throughout the whole sequence of online updates, Lacki and Sankowski [39] gave
an algorithm with $\tilde{O}(n^{5/6})$ worst-case update time per operation.

Partially dynamic algorithms, i.e., algorithms that are restricted to either
edge insertions or deletions only, have also been studied in the context of
exact maintenance of edge connectivity. Henzinger [29] designed an insertions-
only algorithm with $O(\lambda(G)\log n)$ amortized update time. Recently,
Goranci, Henzinger, and Thorup [24] showed how to improve the update time to
$O(\log^{3}n\log\log^{2}n)$, thus removing the dependency on edge connectivity
from the running time.

To summarize, all previous dynamic edge connectivity algorithms either
maintain an approximation to $\lambda(G)$, require that $\lambda(G)$ is small,
handle edges insertions only, or are restricted to special family of graphs
such as planar graphs. Hence, our results are the first fully dynamic exact
edge connectivity algorithms that achieve sub-linear update times on general
graphs.

##  2 Preliminaries

Let $G=(V,E)$ be an $n$-vertex, $m$-edge graph. For a set $U\subseteq V,$ the
_volume_ of $U$ in $G$ is defined as $\mathrm{vol}_{G}(U):=\sum_{u\in U}d(u)$,
where $d(u)$ denotes the degree of $u$ in $G$. Let $\delta=\min_{u\in
U}\\{d(u)\\}$ denote the _minimum degree_ in $G$. A _cut_ is a subset of
vertices $C\subseteq V$ where $\min\\{\left|C\right|,\left|V\setminus
C\right|\\}\geq 1$. A cut $C$ is _non-singleton_ iff
$\min\\{\left|C\right|,\left|V\setminus C\right|\\}\geq 2$. For two disjoint
sets $S,T\subseteq V$, let $E(S,T)\subseteq E$ be the set of edges with one
endpoint in $S$ and the other in $T$. Let $\partial(S):=E(S,V\setminus S)$.
The _edge connectivity_ in $G$, denoted by $\lambda(G)$, is the cut $C$ that
minimizes $\left|\partial(C)\right|$.

It is a well-known fact that edge connectivity can be computed in near-linear
time on the number of edges.

######  Theorem 2.1 ([36])

Let $G=(V,E)$ be a weighted, undirected graph with $m$ edges. There is an
algorithm that computes the edge connectivity $\lambda(G)$ of $G$ in
$\tilde{O}(m)$ time.

##  3 Randomized Algorithm with $\tilde{O}(n)$ Update Time

In this section we prove Theorem 1.1. Our algorithm requires several tools
from different works and we review them below.

##### Random $2$-Out Subgraph and Contraction.

Let $G=(V,E)$ be a undirected simple graph. Let $R=(V,E^{\prime})$ be a
_random $2$-out subgraph_ of $G$ which is obtained from $G$ using the
following procedure

  * •

Set $R\leftarrow(V,E^{\prime})$, where $E^{\prime}\leftarrow\emptyset$.

  * •

For each $u\in V$:

    * $\triangleright~{}$ Sample from $E$ two incident edges $(u,v_{1})$, $(u,v_{2})$ independently, with replacement.

    * $\triangleright~{}$ Add $(u,v_{1})$ and $(u,v_{2})$ to $E^{\prime}$.

The graph $G^{\prime}=G/R$ obtained by contracting all edges of $R$ is called
a _random $2$-out contraction_. Ghaffari, Nowicki and Thorup [22] showed that
a random 2-out contraction reduces the number of nodes to $O(n/\delta)$ whp,
while preserving any fixed non-singleton nearly minimum cut with constant
probability, as in the theorem below.

######  Theorem 3.1 (Theorem 2.4 of [22])

A random $2$-out contraction of a graph with $n$ vertices and minimum degree
$\delta$ has $O(n/\delta)$ vertices, with high probability, and preserves any
fixed non singleton $(2-\epsilon)$ minimum cut, for any constant
$\epsilon\in(0,1]$, with some constant probability $p_{\epsilon}>0$.

##### Sequential and Parallel Constructions of $k$-Connectivity Certificates.

Given a graph $G=(V,E)$, a _$k$ -connectivity certificate_ $H$ of $G$ is a
subgraph of $G$ that preserves all cuts of size at most $k$. Concretely, for
any vertex set $S\subseteq V$, $\min\\{k,|E_{H}(S,V\setminus
S)|\\}=\min\\{k,|E_{G}(S,V\setminus S)|\\}$. Nagamochi and Ibaraki [46]
designed a sequential algorithm for computing a _sparse_ $k$-connectivity
certificate in linear time. Below we shall review an algorithm that does not
run in linear time but it’s simpler and suffices for our purposes.

  * Algorithm 3.@algorithm. (A sequential algorithm for computing a $k$-edge connectivity certificate)

Input: A graph $G=(V,E)$ with $n$ vertices, and a parameter $k$.
Output:  A $k$-connectivity certificate $H$ of $G$.

    1. 1.

Set $G_{1}\leftarrow G$.

    2. 2.

For $i\leftarrow 1,\ldots,k$:

      1. (a)

Find a spanning forest $F_{i}$ of $G_{i}$.

      2. (b)

Set $G_{i+1}\leftarrow G_{i}\setminus F_{i}$.

    3. 3.

Return $H=\cup_{i=1}^{k}F_{i}$.

######  Theorem 3.2 ([46])

Given a graph $G=(V,E)$ with $n$ vertices and an integer parameter $k\geq 1$,
Algorithm 3 returns a $k$-connectivity certificate $H$ of $G$ containing
$O(nk)$ edges.

Observe that Algorithm 3 for constructing a $k$-connectivity certificate
computes $k$ _nested_ spanning forests. When $k$ is large, this long chain of
dependency is too inefficient in the dynamic setting. Although Algorithm 3
will prove useful at some point in our final construction, we need to bypass
this dependency issue. To this end, we will exploit an alternative
$k$-connectivity certificate construction by Daga et al. [10] which was
developed in the context of distributed and parallel algorithms. We describe
this construction in Algorithm 3. The key advantage of this algorithm is that
it reduces the $k$-connectivity certificate problem to $O(k/\log n)$ instances
of $k^{\prime}$-connectivity certificate where $k^{\prime}=O(\log n)$. This
suggests that we can afford using algorithms even with polynomial dependency
on $k^{\prime}$ since $k^{\prime}$ is logarithmic on the number of nodes.

  * Algorithm 3.@algorithm. (A parallel algorithm for computing a $k$-edge connectivity certificate)

Input: A graph $G=(V,E)$ with $n$ vertices, and a parameter $k$.
Output: A $k$-connectivity certificate $H$ of $G$.

    1. 1.

Choose $c\leftarrow k/(4\tau\ln n)$ where $\tau$ is a big enough constant and
$c$ is an integer. Let $k^{\prime}\leftarrow\left\lceil 6\tau\log
n\right\rceil$.

    2. 2.

Randomly color each edge of $G$ using colors from $\\{1,\dots,c\\}$. Let
$E_{i}$ be a set of edges with color $i$. Let $G_{i}=(V,E_{i})$.

    3. 3.

For $i\leftarrow 1,\ldots,c$:

      1. (a)

Apply Algorithm 3 to compute a $k^{\prime}$-connectivity certificate $H_{i}$
of $G_{i}$.

    4. 4.

Return $H=\cup_{i=1}^{c}H_{i}$.

######  Theorem 3.3 (Section 3 of [10])

Given a graph $G=(V,E)$ with $n$ vertices and an integer parameter $k$,
Algorithm 3 returns a subgraph $H$ of $G$ such that (a) $H$ contains $O(nk)$
edges, and (b) $H$ is a $k$-connectivity certificate of $G$ with high
probability.

##### Spanning Forest From $\ell_{0}$-Sampling Sketches.

A well-known tool in the streaming algorithms literature is the
$\ell_{0}$-sampling technique. This tool is particularly useful in the context
of the following natural problem: given a $N$-dimensional vector $x$, we would
like to construct a data structure supporting the following:

  * •

if $x=0$, it reports null,

  * •

if $x\neq 0$, then it returns some $e\in\textrm{support}(x)$ with high
probability,

where $\textrm{support}(x)$ consists of all _non-zero_ entries of $x$. In our
concrete application, $x$ will correspond to a vertex of the graph and we will
store the edges incident to $x$ in such a data structure, i.e.,
$\textrm{support}(x)$ will be the edges incident to $x$. By itself such a data
structure is trivial: just keep an adjacency list for every vertex $x$.
However, for the concrete implementation of the above data structure, we use a
linear function, widely reffered to as a _linear sketching transformation_
(aka linear sketch) $\Pi$, such that given $\Pi(x)$ for $x$ and $\Pi(y)$ for
$y$, we get that $\Pi(x)+\Pi(y)$ gives a data structure that (1) returns an
edge incident to $x$ or $y$ (but not to both) and (2) $\Pi(x)+\Pi(y)$ can be
computed in $\tilde{O}(1)$ time.

More formally, in the theorem below we present the main result relating the
$\ell_{0}$-sampling technique to the above data structure problem and focusing
on running time instead of space guarantees.

######  Theorem 3.4 ([9])

For any dimension parameter $N$, there is a randomized algorithm for
constructing a representation of a linear sketching transformation
$\Pi:\mathbb{R}^{N}\rightarrow\mathbb{R}^{O(\log^{3}N)}$ in $\tilde{O}(1)$
time, such that for any vector $x\in\mathbb{R}^{N}$,

  1. 1.

we can compute $\Pi(x)$ in $\tilde{O}(|\textrm{support}(x)|)$ time, and

  2. 2.

given $\Pi(x)$, we can obtain a _non-zero_ entry of $x$ in $\tilde{O}(1)$ time
with high probability.

The sketch $\Pi$ can be represented using simple hash functions (see [9]) and
avoids explicitly representing $\Pi$ as a matrix of size $O(\log^{3}N)\times
N$. This is why it only takes $\tilde{O}(1)$ to initialize $\Pi$.

We call $\Pi(x)$ an _$\ell_{0}$ -sampling sketch_ of $x$. Our algorithm will
maintain the $\ell_{0}$-sampling sketch of the row-vectors of the signed
vertex-edge incidence matrix of a graph $G$, which is defined as follows.
Given a graph $G=(V,E)$ with $n$ vertices, the _signed vertex-edge incidence
matrix_ $B\in\\{-1,0,1\\}^{n\times\binom{n}{2}}$ of $G$ is

$B_{u,(v,w)}:=\begin{cases}1&(v,w)\in E\text{ and }u=v\\\ -1&(v,w)\in E\text{
and }u=w\\\ 0&\text{otherwise.}\end{cases}$

Let $b_{u}\in\\{-1,0,1\\}^{\binom{n}{2}}$ denote the $u$-th row of $B$. We
observe that one can efficiently compute and update the sketches $\Pi(b_{u})$
for all $u\in V$.

###### Proposition 3.1

Given a $n$-vertex graph $G$ with $m$ edges, there is an algorithm to compute
a linear transformation $\Pi(b_{u})$ for all $u\in V$ in $\tilde{O}(m)$ time.
Upon an edge insertion or deletion in $G$, one can update the sketches
$\Pi(b_{u})$ for all $u\in V$ in $\tilde{O}(1)$ time.

  * Proof.

When computing $\Pi(b_{u})$, we only spend
$\tilde{O}(|\textrm{support}(b_{u})|)$ time by Theorem 3.4 (1). Since the
incidence matrix $B$ contains only $\sum_{u}|\textrm{support}(b_{u})|=O(m)$
non-zeros, the first claim of the proposition follows. The second claim holds
since (i) each edge update affects only two entries of $B$ and (ii) $\Pi$ is a
linear transformation. Concretely, let $(u,v)$ be the updated edge and let
$e_{u}$ and $e_{v}$ be the elementary unit vectors with the non-zero entry
only at $u$ and $v$, respectively. We start by computing $\Pi(e_{u})$ and
$\Pi(e_{v})$ in $\tilde{O}(1)$ time, and then proceed to evaluating
$\Pi(b_{u})\pm\Pi(e_{u})$ and $\Pi(b_{v})\mp\Pi(e_{v})$ in $\tilde{O}(1)$
time, where the sign depends on whether $(u,v)$ is inserted or deleted.

The sketches $\Pi(b_{u})$ for all $u\in V$ are particularly useful since for
any given any set $S\subseteq V$, they allow us to obtain an edge crossing the
cut $(S,V\setminus S)$ in $\tilde{O}(|S|)$ time. This is better than the
trivial approach which scans through all edges incident to $S$ and takes
$O(|S|^{2}+|E(S,V\setminus S)|)$ time in the worst case. More formally, let
$b_{S}:=\sum_{u\in S}b_{u}$ for any vertex set $S\subseteq V$. Now, by Theorem
3.4 each $\Pi(b_{u})$ can be queried in $\tilde{O}(1)$ time. Using the
linearity of $\Pi$, we compute $\Pi(b_{S})=\sum_{u\in S}\Pi(b_{u})$ in
$\tilde{O}(|S|)$ time. Observing that non-entries of $b_{S}$ correspond
exactly to the edges crossing the cut $(S,V\setminus S)$, we can obtain one of
these edges from $\Pi(b_{S})$ in $\tilde{O}(1)$ time. This observation has
proven useful for building a spanning forest of a graph $G$ in $\tilde{O}(n)$
time444Note that this sub-linear in the size of the graph since $G$ has $m$
edges when give access to the sketches $\Pi(b_{u})$, $u\in V$. More precisely,
it is implicit in previous works [2, 33] that if $O(\log n)$ _independent_
copies of the sketches are maintained, then a spanning forest can be
constructed using Boruvka’s algorithm, as summarized in the theorem below.

######  Theorem 3.5 ([2, 33])

Let $G=(V,E)$ be an $n$-vertex graph. Let $\Pi_{1},\ldots,\Pi_{O(\log n)}$ be
linear transformations for the $\ell_{0}$-sampling sketch from Theorem 3.4
generated independently. Let $\Pi_{i}(b_{u})$ be the sketches for all vertices
$u\in S$ and all $i=1,\ldots,O(\log n)$. Then there is an algorithm to
construct a spanning forest of $G$ in $\tilde{O}(n)$ time with high
probability.

##### Sum of $\ell_{0}$-Sampling Sketches via Dynamic Tree.

Suppose our goal is to maintain a data structure for a (not necessarily
spanning) forest $F$ of a graph $G$. We next review a result that allows us to
a build a data structure on $F$ such that for any connected component $S$ of
$F$, we can compute $\Pi(b_{S})$ in $\tilde{O}(1)$ time, which is faster than
the previous approach that yielded an $\tilde{O}(|S|)$ time algorithm by
explicitly summing $\sum_{u\in V}\Pi(B_{u})$. This construction is implicit in
[33] and can be alternatively obtained by combining Theorem 4.16 of [47] with
Theorem 3.4 and Proposition 3.1.

###### Theorem 3.6

Let $\Pi$ be a linear transformation for the $\ell_{0}$-sampling sketch from
Theorem 3.4. There is a data structure $\mathcal{D}(\Pi,G,F)$ that maintains
an $n$-vertex graph $G=(V,E)$ and a (not necessarily spanning) forest $F$ on
the same vertex set $V$ that supports the following operations

  * •

insert or delete an edge in $G$ in $\tilde{O}(1)$ time,

  * •

insert or delete an edge in $F$ (as long as $F$ remains a forest) in
$\tilde{O}(1)$ time, and

  * •

given a pointer to a connected component $S$ of $F$, return
$\Pi(b_{S})=\sum_{u\in V}\Pi(b_{u})$, where $b_{u}$ is the $u$-th row of the
incidence matrix $B$ of $G$, in $\tilde{O}(1)$ time.

###  3.1 The Algorithm

In this section, we show an algorithm for maintaining the edge connectivity of
an $n$-vertex dynamic graph undergoing edge insertions and deletions in
$\tilde{O}(n)$ worst-case update time with high probability, i.e., we prove
Theorem 1.1.

Let $G$ be a graph undergoing edge insertions and deletions. We make the
following two simplifying assumptions

  1. (1)

the edge connectivity is attained at a _non-singleton_ minimum cut $C^{*}$ of
$G$, and

  2. (2)

the minimum degree $\delta$ of $G$ is between some fixed range
$[\delta_{0}/2,\delta_{0}]$, and we shall construct a data structure depending
on $\delta_{0}$.

We lift (1) by observing that if this assumption doesn’t hold, then we have
that the edge connectivity $\lambda=\delta$, and the minimum degree $\delta$
of $G$ can be maintained in a straightforward way. Assumption (2) can be
lifted by constructing $O(\log n)$ data structures for the ranges
$[2^{i},2^{i+1}]$ for $i\leq\log n+1$, and query the data structure for range
$[2^{i},2^{i+1}]$ whenever $\delta\in[2^{i},2^{i+1}]$.

Before we proceed further, recall that $R$ is a random 2-out subgraph and
$G^{\prime}=G/R$ is the random 2-out contraction of $G$. By Theorem 3.1, the
minimum cut $C^{*}$ is preserved in $G^{\prime}$ with some positive constant
probability. We can boost this to a high probability bound by repeating the
whole algorithm $O(\log n)$ times. As $G^{\prime}$ contains $O(n/\delta_{0})$
vertices with high probability, throughout we will also assume that this is
the case.

Despite the size guarantee on the vertex set of $G^{\prime}$, maintaining
$G^{\prime}$ and running a static edge connectivity algorithm on $G^{\prime}$
is not enough as the number of edges in $G^{\prime}$ could potentially be
large. This leads us to the main component of our data structure that instead
maintains a $\delta_{0}$-connectivity certificate $H^{\prime}$ of $G^{\prime}$
while supporting updates as well as querying $H^{\prime}$ in $\tilde{O}(n)$
update time.

###### Theorem 3.7

Let $G$ be a dynamic graph and let $G^{\prime}$ be the random $2$-out
contraction of $G$. Let $\delta_{0}$ be an integer parameter such that
$n\geq\delta_{0}>\lambda$. There is a data structure that supports edges
updates to $G$ (and thus to $G^{\prime}$) and gives query access to a
$\delta_{0}$-connectivity certificate $H^{\prime}$ of $G^{\prime}$ containing
$\tilde{O}(n)$ edges with high probability. The updates can be implemented in
$\tilde{O}(\delta_{0})$ worst-case time, the queries in $\tilde{O}(n)$ worst-
case time.

We claim that Theorem 3.7 proves Theorem 1.1. To see this, recall that
$H^{\prime}$ preserves all cuts of size at most $\delta_{0}$ in $G^{\prime}$
by the definition of $\delta_{0}$-connectivity certificate. By our assumption
$\lambda<\delta_{0}$, this implies that the minimum cut $C^{*}$ is preserved
in $H^{\prime}$ and suggests that we can simply run a static edge connectivity
algorithm on top of $H^{\prime}$ to find $C^{*}$ in
$\tilde{O}(|E(H^{\prime})|)=\tilde{O}(n)$ time. Therefore, the rest of this
section is devoted to proving Theorem 3.7.

The first component of the data-structure is to maintain (i) a random 2-out
subgraph $R$ of $G$ and (ii) a spanning forest $F$ of $R$. By the definition
of $R$, (i) can be implemented in $O(1)$ worst-case update time per edge
update. For (ii), we use the dynamic spanning forest data structure of Kapron,
King and Mountjoy [33] that guarantees a $\tilde{O}(1)$ worst-case update
time. Since for each edge update to $G$, there are only $O(1)$ edge updates to
$R$, this can be implemented in $\tilde{O}(1)$ worst-case time per edge update
as well. We use the following two-step approach to prove our result

  1. (1)

reducing the dynamic $\delta_{0}$-connectivity certificate problem to the
dynamic $O(\log n)$-connectivity certificate problem via the template
presented in Theorem 3, and

  2. (2)

solving the dynamic $O(\log n)$-connectivity certificate problem using the
linear sketching tools developed in the previous section.

##### Reducing $\delta_{0}$-Connectivity Certificates to $O(\log
n)$-Connectivity Certificates.

We follow the template of Algorithm 3 from Theorem 3.3: Set $k=\delta_{0}$ and
let $c=k/(4\tau\ln n)$ and $k^{\prime}=\left\lceil 6\tau\log n\right\rceil$ be
defined as in Algorithm 3. Then, color each edge of $G$ by randomly choosing a
color from $\\{1,\dots,c\\}$. Let $G_{i}$ be the subgraph of $G$ containing
edges of color $i$. We observe that all graphs $G_{i}$ can be maintained
explicitly together with $G$ with in $\tilde{O}(1)$ time per edge update.
Similarly, let $G^{\prime}_{i}$ be the subgraph of the random $2$-out
contraction $G^{\prime}$ containing edges of color $i$, i.e.,
$G^{\prime}_{i}=G^{\prime}\cap G_{i}$.

Our goal is to not explicitly maintain $G^{\prime}_{i}$, but instead build a
dynamic data structure with $\tilde{O}(1)$ worst-case update time per edge
update in $G$ that gives query access to a $k^{\prime}$-connectivity
certificate $H^{\prime}_{i}$ of $G^{\prime}_{i}$ in $\tilde{O}(n/\delta_{0})$
time with high probability.

We claim that this suffices to prove Theorem 3.7. To see this, note that for
each $i=1,\ldots,c$ we can query $H^{\prime}_{i}$ in $\tilde{O}(n/\delta_{0})$
time. Then we simply union all these certificates to compute
$H^{\prime}=\cup_{i=1}^{c}H^{\prime}_{i}$ in
$c\cdot\tilde{O}(n/\delta_{0})=\delta_{0}/(4\tau\ln
n)\cdot\tilde{O}(n/\delta_{0})=\tilde{O}(n)$ time, which bounds the query
time. To bound the update time, note that the worst-case cost for maintaining
these $c$ data structures is $c\cdot\tilde{O}(1)=\tilde{O}(\delta_{0})$. By
Theorem 3.3 it follows that (i) $H^{\prime}$ is indeed a
$\delta_{0}$-connectivity certificate $H^{\prime}$ of $G^{\prime}$ and (ii)
the size of $H^{\prime}$ is at most $\delta\cdot O(n/\delta)=O(n)$, which
completes the proof of Theorem 3.7.

#####  $O(\log n)$-Connectivity Certificates of $G^{\prime}_{i}$ via Linear
Sketching.

Let us fix a color $i=1,\ldots,c$. Recall that our goal is to obtain a $O(\log
n)$-connectivity certificate $H^{\prime}_{i}$ of $G^{\prime}_{i}$ in time
$\tilde{O}(n/\delta_{0})$ per query and $\tilde{O}(1)$ per edge update.

Recall that $G_{i}$, which is the graph containing all color-$i$ edges of $G$,
is explicitly maintained. Let $F$ be a spanning forest of the random 2-out
subgraph $R$ which we also maintain explicitely as discussed above. For all
$j,\ell=1,\ldots,O(\log n)$, we independently generate the linear
transformation for a $\ell_{0}$-sampling sketch $\Pi^{(j,\ell)}$ using Theorem
3.4. For each index pair $(j,\ell)$, we build a data structure ${\cal
D}^{(j,\ell)}:={\cal D}(\Pi^{(j,\ell)},G_{i},F)$555Here we deliberately omit
the subscript $i$ from ${\cal D}^{(j,\ell)}$ since the color $i$ was fixed in
the beginning of the paragraph and this omission simplifies the presentation.
and maintain whenever $G$ or $F$ changes using Theorem 3.6. Since for each
edge update to $G$, there are only $O(1)$ edge updates to $G_{i}$ and $F$,
respectively, we can maintain all ${\cal D}^{(j,\ell)}$’s in $\tilde{O}(1)$
worst-case update time per edge update to $G$. This completes the description
of handling edge updates and its running time analysis.

It remains to show how to query a $O(\log n)$-connectivity certificate
$H^{\prime}_{i}$ of $G^{\prime}_{i}$ using ${\cal D}^{(j,\ell)}$ in
$\tilde{O}(n/\delta_{0})$ time. The main idea of our construction is the
following simple but crucial observation. Each vertex $u$ in $G^{\prime}_{i}$
corresponds to a tree $S_{u}$ of $F$ as $S_{u}$ is contracted into $u$. The
latter holds by the definition of $G^{\prime}_{i}$. Therefore, if we let $B$
and $B^{\prime}$ denote the incidence matrices of $G_{i}$ and
$G^{\prime}_{i}$, respectively, then we have $b_{S_{u}}=b^{\prime}_{u}$. Now,
using the data structures ${\cal D}^{(j,\ell)}$ we can retrieve
$\Pi^{(j,\ell)}(b_{S})$ for all components $S$ of $F$, which in turn gives us
$\Pi^{(j,\ell)}(b^{\prime}_{u})$ for all $u\in V(G^{\prime}_{i})$. Note that
the total time to query ${\cal D}^{(j,\ell)}$ for all $j,\ell=1,\ldots,O(\log
n)$ and all $u\in V(G^{\prime}_{i})$ is
$\tilde{O}(|V(G^{\prime}_{i})|)=\tilde{O}(n/\delta_{0})$.

Now, the sketches $\Pi^{(j,\ell)}(b^{\prime}_{u})$ for all $u\in
V(G^{\prime}_{i})$ and all $j,\ell=1,\ldots,O(\log n)$ allow us to compute
$O(\log n)$-connectivity certificate $H^{\prime}_{i}$ of $G^{\prime}_{i}$ as
shown below. Note that the algorithms modifies the sketches
$\Pi^{(j,\ell)}(b^{\prime}_{u})$ but we may revert the sketches back to their
initial state after computing and returning $H^{\prime}_{i}$.

We finally explain the procedure for querying $H^{\prime}_{i}$. To this end,
we follow the template of Theorem 3 from Theorem 3.2. Set
$G_{1}^{tmp}\leftarrow G^{\prime}_{i}$ to be the temporary graph that we will
work with. Consider the $j$-th round of the algorithm where $j=1,\ldots,O(\log
n)$. We compute a spanning forest $F_{j}$ of $G_{j}^{tmp}$ using the sketches
$\Pi^{(j,1)},\dots,\Pi^{(j,\log n)}$ on vertices of $G^{\prime}_{i}$ in
$\tilde{O}(|V(G^{\prime}_{i})|)=\tilde{O}(n/\delta_{0})$ time using Theorem
3.5. Next, we update $G_{j+1}^{tmp}\leftarrow G_{j}^{tmp}\setminus F_{j}$ and
also update the sketches $\Pi^{(j^{\prime},\ell)}$ for all $j^{\prime}>j$ so
that they maintain information of graph $G_{j+1}^{tmp}$ and not of
$G_{j}^{tmp}$. This takes $\tilde{O}(n/\delta_{0})$ time because $F_{j}$
contains $\tilde{O}(n/\delta_{0})$ edges. This ends the $j$-th round. After
all rounds have been completed, we return $H^{\prime}_{i}=\cup_{j}F_{j}$ which
is a $O(\log n)$-connectivity certificate by Theorem 3.2. Since there are
$O(\log n)$ iterations, the total query time is $\tilde{O}(n/\delta_{0})$,
what we wanted to show. Note that algorithm internally stores the edge
connectivity value only and not the edges on a cut that attains the edge
connectivity. Therefore, the adversary cannot reveal anything useful from
querying this information, and thus it follows that our algorithm works
against an adaptive adversary.

##  4 Deterministic Algorithm with $O(m^{1-\varepsilon})$ Update Time

In this section we prove Theorem 1.2. Our algorithm requires several tools
from different works and we review them below.

##### Expander Decomposition and Pruning.

The key to our approach is the notion of _expander_ graphs. The _conductance_
of an unweighted, undirected graph is defined by

$\Phi(G):=\min_{\emptyset\subset S\subset
V}\partial(S)/\min\\{\mathrm{vol}_{G}(S),\mathrm{vol}_{G}(V\setminus S)\\}.$

We say that a graph $G$ is $\phi$-_expander_ if $\Phi(G)\geq\phi$. Next, we
introduce the notion of expander decomposition.

######  Definition 4.1 (Expander Decomposition)

Let $G=(V,E)$ be an undirected, unweighted graph and let $\phi\in(0,1)$ be a
parameter. A _$\phi$ -expander decomposition_ of $G$ is a _vertex-disjoint_
partitioning $\mathcal{U}=\\{U_{1},\ldots,U_{k}\\}$ of $V$ such that

  * •

$\sum_{1\leq i\leq k}\left|\partial(U_{i})\right|=O(\phi m)$, and

  * •

for each $1\leq i\leq k$, $\Phi(G[U_{i}])\geq\phi$.

We now review an efficient algorithm for finding expander decompositions.

######  Theorem 4.1 ([54])

Let $G=(V,E)$ be an undirected, uniweighted graph and let $\phi\geq 0$ be a
parameter. There is an algorithm Expander$(G,\phi)$ that in
$\tilde{O}(m/\phi)$ time finds a $\phi$-expander decomposition.

The next result allows us to turn static expander decompositions into their
dynamic variants, as shown in Section 4.1

######  Theorem 4.2 (Expander Pruning, [54])

Let $G=(V,E)$ be an undirected, unweighted $\phi$-expander. Given an online
sequence of $k\leq\phi\mathrm{vol}(G)/20$ edge deletions in $G$, there is an
algorithm that maintains a _pruned set_ $P\subseteq V$ satisfying the
following properties; let $G_{i}$ and $P_{i}$ be the graph $G$ and the set $P$
after the $i$-th deletion. For $1\leq i\leq k$,

  1. 1.

$P_{0}=\emptyset$ and $P_{i}\subseteq P_{i+1}$,

  2. 2.

$\mathrm{vol}_{G}(P_{i})\leq 8i/\phi$ and $|\partial(P_{i})|\leq 4i$, and

  3. 3.

$G_{i}[V\setminus P_{i}]$ is a $\phi/6$-expander.

The total time for updating $P_{0},\ldots,P_{k}$ is $O(k\log m/\phi^{2})$.

##### Non-singleton Minimum Cut Sparsifiers.

Our algorithm relies on sparsifiers that preserve non-singleton cuts of simple
graphs.

###### Definition 4.2

Let $G=(V,E)$ be an undirected, unweighted graph. A multi-graph
$H=(V^{\prime},E^{\prime})$ is a _non-singleton minimum cut sparsifiers_ _(_
abbrv. _NMC sparsifier_ _)_ of $G$ if $H$ preserves all non-singleton minimum
cuts of $G$, i.e., for all cuts $C\subset V$ with $\min\\{|C|,|V\setminus
C|\\}\geq 2$ and $\partial_{G}(C)=\lambda(G)$,

$\left|\partial_{H}(C)\right|=\left|\partial_{G}(C)\right|.$

We say that $H$ is of size $k$ if $|E^{\prime}|\leq k$.

Kawarabayashi and Thorup [38] showed that undirected, simple graphs admit NMC
sparsifiers of size $\tilde{O}(m/\delta)$. They also designed a deterministic
$\tilde{O}(m)$ time algorithm for computing such sparsifiers. We will
construct NMC sparsifiers that are based on expander decompositions, following
the work of Saranurak [53], as we can turn them into a dynamic data structure.
To do so, we need to formally define the procedures of _trimming_ and
_shaving_ vertex subsets of a graph.

######  Definition 4.3 (Trim and Shave)

Let $U$ by any vertex subset in $G=(V,E)$. Define $\mathrm{trim}(U)\subseteq
U$ to be the set obtained by the following procedure: while there exists a
vertex $u\in U$ with $|E(u,U)|<\frac{2}{5}d(u)$, remove $u$ from $U$. Let
$\mathrm{shave}(U)=\\{u\in U\mid|E(u,U)|>\frac{1}{2}d(u)+1\\}$.

Observe that the trimming procedure recursively removes a vertex with few
connections inside the _current_ set $U$ while the shaving procedure removes
all vertices with few connections inside the _initial_ set $U$. Saranurak [53]
showed that we can construct NMC sparsifiers by applying triming and shaving
to each cluster in the expander decomposition. We formally summarize his
construction in the lemma below.

######  Lemma 4.1 ([53])

Let $G=(V,E)$ be an undirected, simple graph with $m$ edges, and let
$\phi=c/\delta$, where $\delta$ is the minimum degree in $G$ and $c\geq 40$
some positive constant. Let

$\mathcal{U}=\textsc{Expander}(G,\phi),~{}\mathcal{U}^{\prime}=\\{\mathrm{trim}(U)\mid
U\in\mathcal{U}\\}\text{ and
}\mathcal{U}^{\prime\prime}=\\{\mathrm{shave}(U^{\prime})\mid
U^{\prime}\in\mathcal{U^{\prime}}\\}.$

Let $H=(V^{\prime},E^{\prime})$ be the graph obtained from $G$ by contracting
every set $U^{\prime\prime}\in\mathcal{U}^{\prime\prime}$. Then $H$ is an NMC
sparsifier of size $\tilde{O}(\phi m)$ for $G$. The running time for computing
$H$ is $\tilde{O}(m)$.

###  4.1 Decremental Expander Decomposition

In this section we show that the expander pruning procedure from Theorem 4.2
allows us to design a dynamic algorithm for maintaining an expander
decomposition under edge deletions. While the theorem below is already
implicit in other works leveraging the power of expander decompositions [25,
5] (albeit with slightly different guarantees and variations depending on the
specific application), here we give a simple, self-contained version that
suffices to solve the edge connectivity problem.

###### Theorem 4.3

Given an unweighted, undirected graph $G=(V,E)$ with $m$ edges and a parameter
$\phi\in(0,1)$, there is a decremental algorithm that supports an online
sequence of up to $\phi^{2}m$ edge deletions and maintains a $\phi/6$-expander
decomposition in $\tilde{O}(m/\phi)$ total update time.

We initialize our data structure by (i) constructing a $\phi$-expander
decomposition $\mathcal{U}$ of the initial graph $G$ using Theorem 4.1, where
$\phi\in(0,1)$ is a parameter, and (ii) starting a pruning data-structure
$\mathcal{D}(U)$ for each expander $U\in\mathcal{U}$ using Theorem 4.2. We
also maintain a counter $\\#\mathrm{del}(U)$ that denotes the number of edge
deletions inside the cluster $U$. Initially, $\\#\mathrm{del}(U)=0$ for each
$U\in\mathcal{U}$. If the total number of edge deletions exceeds $\phi^{2}m$,
our data-structure terminates.

We next show how to handle edge deletions. Consider the deletion of edge $e$
from $G$. If $e$ is an inter-cluster edge in $\mathcal{U}$, then we simply
remove it from $G$ since its removal does not affect the expansion of any of
the clusters in $\mathcal{U}$. Otherwise, $e$ is an intra-cluster edge, and
let $U_{e}\in\mathcal{U}$ be the unique cluster that contains $e$. First, we
increase the counter $\\#\mathrm{del}(U_{e})$ by $1$. Next we compare the
number of deletions in the cluster relative to the number of deletions the
pruning procedure can handle.

Concretely, if $\\#\mathrm{del}(U_{e})\leq\phi\mathrm{vol}_{G}(U_{e})/20$, we
pass the deletion of $e$ to the pruning data structure $\mathcal{D}(U_{e})$.
Let $P_{i}$, resp., $P_{i-1}$ be the pruned set that $\mathcal{D}(U_{e})$
maintains after, resp. before the deletion $e$. We define $S=\\{\\{u\\}\mid
u\in P_{i}\setminus P_{i-1}\\}$ to be the set of singleton clusters, and then
replace $U_{e}$ in $\mathcal{U}$ with $\\{U_{e}\setminus\\{P_{i}\setminus
P_{i-1}\\},S\\}$. The last step can be thought of as including every vertex in
$P_{i}\setminus P_{i-1}$ as a singleton cluster in $\mathcal{U}$ and removing
these vertices from the current expander $U_{e}$.

However, if $\\#\mathrm{del}(U_{e})>\phi\mathrm{vol}_{G}(U_{e})/20$, then we
declare every vertex in the current cluster $U_{e}$ to be a singleton cluster.
Specifically, we remove $U_{e}$ from $\mathcal{U}$ and for each $u\in U_{e}$,
add $\\{u\\}$ to $\mathcal{U}$. Note that the latter implies that all vertices
that belonged to the _original_ cluster $U_{e}$ are included as singletons in
the current expander decomposition. This completes the description of the
procedure for deleting an edge.

We next show that the above algorithm correctly maintains an expander
decomposition under edge deletions while paying a small constant factor in the
expansion guarantee of each cluster and in the number of inter cluster edge.

######  Lemma 4.2 (Correctness)

The decremental algorithm maintains a $\phi/6$-expander decomposition.

  * Proof.

Let $\mathcal{U}$ be expander decomposition that the algorithm maintains for
the current graph $G$.

Our first goal is to show that for each $U\in\mathcal{U}$,
$\Phi(G[U])\geq\phi/6$. Observe that by construction each cluster $U$ in
$\mathcal{U}$ can either be (i) a singleton, (ii) a pruned cluster (i.e., a
cluster that is formed by removing vertices from the original cluster) or
(iii) an original cluster from the initial expander decomposition. If a
cluster is a singleton, then the expansion bound trivially holds. If we have a
type (ii) cluster, then by expander pruning (Theorem 4.2, Property 3), it
follows that $\Phi(G[U])\geq\phi/6$, where $G$ is the current graph. Finally,
for a type (iii) cluster, the initial expander decomposition (Theorem 4.1)
gives that $\Phi(G[U])\geq\phi\geq\phi/6$. Combining the above cases, leads to
the expansion bound we were after.

We now bound the number of inter cluster edges in $\mathcal{U}$. Recall that
initially, the expander decomposition has at most $O(\phi m)$ inter-cluster
edges (Theorem 4.1). During the handling of edge deletions, the algorithm
introduces new inter-cluster edges when vertices from the pruned set are
included as singletons. Thus, our ultimate goal is to bound the volume of the
pruned set with the number of edge deletions in a cluster. To this end, let
$U$ be a cluster in $\mathcal{U}$. We distinguish two cases. If
$\\#\mathrm{del}(U)\leq\phi\mathrm{vol}_{G}(U)/20$ then, then by expander
pruning (Theorem 4.2, Property 2) we have that the maintained pruned set
$P_{U}$ satisfies $\mathrm{vol}(P_{U})\leq 8\cdot\\#\mathrm{del}(U)/\phi$.
However, if $\\#\mathrm{del}(U)>\phi\mathrm{vol}_{G}(U)/20$, then by
construction, the pruned set $P_{U}$ is the entire original cluster $U$. By
rearranging the inequality in the last condition, we get
$\mathrm{vol}(P_{U})=\mathrm{vol}(U)\leq 20\cdot\\#\mathrm{del}(U)/\phi$.
Combining the above bounds, we get that at any time during our decremental
algorithm, the volume of the maintained pruned set of a cluster satisfies
$\mathrm{vol}(P_{U})=\mathrm{vol}(U)\leq 20\cdot\\#\mathrm{del}(U)/\phi$.

Summing this over all clusters in the expander decomposition $\mathcal{U}$, we
have the number of the new inter-cluster edges is bounded by

$\sum_{U\in\mathcal{U}}\mathrm{vol}(P_{U})\leq\frac{20}{\phi}\sum_{U\in\mathcal{U}}\\#\mathrm{del}(U)\leq\frac{20}{\phi}\phi^{2}m=O(\phi
m),$

where the penultimate inequality follows from the fact the number of edge
deletions to $G$ is bounded by $\phi^{2}m$ by the assumption of the lemma.
Thus, the number of inter-cluster edges increases by a constant multiplicative
factor, which concludes the proof of the lemma.

We next bound the running time of our decremental algorithm.

######  Lemma 4.3 (Running Time)

The decremental expander decomposition runs in $\tilde{O}(m/\phi)$ total
update time.

  * Proof.

The running time of the algorithm is dominated by (1) the time required to
compute the initial expander decomposition and (2) the total time to perform
expander pruning on each cluster of this decomposition. By Theorem 4.1, (1) is
bounded by $\tilde{O}(m/\phi)$. By Theorem 4.2, the pruning process on a
cluster $U$ can be implemented in $\tilde{O}(\phi\mathrm{vol}_{G}(U)\cdot\log
m/\phi^{2})=\tilde{O}(\mathrm{vol}_{G}(U)/\phi)$. Summing over all the
clusters in the expander decomposition $\mathcal{U}$ and recalling that they
form a partition of $V(G)$, we get that the running time of (2) is bounded by

$\sum_{U\in\mathcal{U}}\tilde{O}(\mathrm{vol}_{G}(U)/\phi)=\tilde{O}(m/\phi).$

Bringing together (1) and (2) proves the claim of the lemma.

###  4.2 Fully Dynamic NMC sparsifier

In this section present a fully dynamic algorithm for maintaining a NMC
sparsifier of undirected, simple graphs.

####  4.2.1 Decremental NMC sparsifier

We start by showing that the decremental expander decomposition (Theorem 4.3)
almost immediately yields a decremental algorithm for maintaining a NMC
sparsifier. More specifically, we show the following theorem in this
subsection.

###### Theorem 4.4

Given an unweighted, undirected graph $G=(V,E)$ with $m$ edges and a parameter
$\phi\in(0,1)$ satisfying $\phi\geq c/\delta$ for some positive constant
$c\geq 240$, there is a decremental algorithm that supports an online sequence
of up to $\phi^{2}m$ edge deletions and maintains a NMC sparsifier $H$ of size
$\tilde{O}(\phi m)$ in $\tilde{O}(m/\phi)$ total update time.

Let $\phi\in(0,1)$ be parameter with $\phi\geq c/\delta$ for some positive
constant $c\geq 240$. Our data-structure internally maintains an expander
decomposition under edge deletions DecExpander$(G,\phi)$ (Theorem 4.3). Let
$\mathcal{U}_{(0)}$ be the expander decomposition of the initial graph
$G^{(0)}$ from DecExpander$(G,\phi)$. Let
$\mathcal{U}_{(0)}^{\prime}=\\{\mathrm{trim}(U)\mid U\in\mathcal{U}_{(0)}\\}$
and $\mathcal{U}_{(0)}^{\prime\prime}=\\{\mathrm{shave}(U^{\prime})\mid
U^{\prime}\in\mathcal{U}^{\prime}_{(0)}\\}$. We define
$H^{(0)}=(V^{\prime},E^{\prime})$ to be the graph obtained from $G^{(0)}$ by
contracting every set $U^{\prime\prime}\in\mathcal{U}_{(0)}^{\prime\prime}$.
As we will shortly see, $H^{(0)}$ will correspond to a NMC sparsifier of
$G^{(0)}$. This suggests that in order to maintain such a sparsifier under
edge deletions we need to efficiently maintain the sets
$U^{\prime}=\mathrm{trim}(U)$ and
$U^{\prime\prime}=\mathrm{shave}(U^{\prime})$ for every cluster $U$ in the
current expander decomposition $\mathcal{U}$. We achieve this by keeping track
of the following counters:

  * •

the degree $\deg(u)$ of each vertex $u$ in $V$, and

  * •

the degree $\deg_{U^{\prime}}(u):=|E(u,U^{\prime})|$ for all $u\in U^{\prime}$
and all $U^{\prime}\in\mathcal{U^{\prime}}$, i.e., the degree of vertex $u$
restricted to the cluster $U^{\prime}$.

Note that both degree values can be computed for each vertex in the initial
graph $G_{0}$ by performing a graph traversal.

Now, consider the deletion of an edge $e=(u,v)$ from $G$. We first decrement
the value of both counters $\deg(u)$ and $\deg(v)$ by one to account for the
deletion of $e$. Then we pass this deletion to the data-structure
$\textsc{DecExpander}(G,\phi)$. This in turn reports a subset of vertices
$P_{U}$ that are pruned out of a cluster $U$ due to the deletion of $e$. At
this point observe that the decremental expander decomposition algorithm
already has updated $U$ with respect to $P_{U}$. Thus it remains to update the
sets $U^{\prime}$ and $U^{\prime\prime}$ respectively.

For each $u\in P_{U}$ we do the following. First, note that when $u\not\in
U^{\prime}$, we don’t need to do anything since $U^{\prime\prime}\subseteq
U^{\prime}$ asserts that $u$ cannot belong to the contracted set
$U^{\prime\prime}$. If $u\in U^{\prime}$, then we remove $u$ from $U^{\prime}$
and potentially $U^{\prime\prime}$ by invoking the subprocedure
$\textsc{Remove}(u)$ defined as follows:

  * Remove$(u)$

  * $\quad\bullet~{}$ Set $U^{\prime}_{\mathrm{old}}\leftarrow U^{\prime}$, and set $U^{\prime}\leftarrow U^{\prime}\setminus\\{u\\}$.

  * $\quad\bullet~{}$ If $u\in U^{\prime\prime}$ then

    * $\quad\triangleright~{}$ Set $U^{\prime\prime}\leftarrow U^{\prime\prime}\setminus\\{u\\}$, and $\textsc{Uncontract}(u)$

  * $\quad\bullet~{}$ For every neighbour $v\in E(u,U^{\prime}_{\mathrm{old}})$:

    * $\quad\triangleright~{}$ Set $\deg_{U^{\prime}}(v)\leftarrow\deg_{U^{\prime}}(v)-1$.

    * $\quad\triangleright~{}$ If $\deg_{U^{\prime}}(v)<2/5\deg(v)$ then

      * $\quad-~{}$ $\textsc{Remove}(v)$

    * $\quad\triangleright~{}$ If $\deg_{U^{\prime}}(v)<\deg(v)/2+1$ and $v\in U^{\prime\prime}$ then

      * $\quad-~{}$ Set $U^{\prime\prime}\leftarrow U^{\prime\prime}\setminus\\{v\\}$, and $\textsc{Uncontract}(v)$.

Procedure Uncontract$(u)$ simply reverts the operation of contracting $u$ into
some cluster $U^{\prime\prime}$. It can also be interpreted as adding the
vertex $u$ together with its incident edges in $G$ to the current sparsifier
$H$. This completes the description of the algorithm.

The next lemma shows that the algorithm maintains a sparsifier that preserves
non-singleton minimum cuts exactly.

######  Lemma 4.4 (Correctness)

The decremental algorithm correctly maintains a NMC sparsifier $H$ of size
$O(\phi m)$.

  * Proof.

We begin by showing that $H$ is a NMC sparsifier of some current graph $G$. To
this end, let $G^{(i)}$ be the graph after the $i$-th deletion and let
$H^{(i)}$ be the sparsifier after the data-structure has processed the $i$-th
deletion. To prove that $H^{(i)}$ is a NMC sparsifier of $G^{(i)}$ it suffices
to show that (i) $\mathcal{U}^{(i)}$ is $\phi/6$-expander decomposition of
$G^{(i)}$ (ii) ${\mathcal{U}_{(i)}}^{\prime}=\\{\mathrm{trim}(U)\mid
U\in\mathcal{U}_{(i)}\\}$, and (iii)
$\mathcal{U}_{(i)}^{\prime\prime}=\\{\mathrm{shave}(U^{\prime})\mid
U^{\prime}\in\mathcal{U}_{(i)}^{\prime}\\}$. To see why this is true, note
that $\phi/6\geq 240/(6\delta)\geq 40/\delta$ by assumption of Theorem 4.4,
and apply Lemma 4.1 with the parameter $\phi/6$.

If $i=0$, recall that by construction $\mathcal{U}_{(0)}$ is a $\phi$-expander
decomposition of the initial graph $G^{(0)}$,
$\mathcal{U}_{(0)}^{\prime}=\\{\mathrm{trim}(U)\mid U\in\mathcal{U}_{(0)}\\}$
and $\mathcal{U}_{(0)}^{\prime\prime}=\\{\mathrm{shave}(U^{\prime})\mid
U^{\prime}\in\mathcal{U}^{\prime}_{(0)}\\}$. Since the parameter $\phi$
satisfies $\phi\geq 240/\delta\geq 40/\delta$, we get the graph $H^{(0)}$
obtain by contracting every set
$U^{\prime\prime}\in\mathcal{U}^{\prime\prime}_{(0)}$ is a NMC sparsifier of
$G^{(0)}$.

If $i\geq 1$, inductively assume that
$\mathcal{U}_{(i-1)},\mathcal{U}^{\prime}_{(i-1)},\mathcal{U}^{\prime\prime}_{(i-1)}$
have been correctly maintained until the $(i-1)$-st edge deletion. By Theorem
4.3, we already know that $\mathcal{U}_{(i)}$ is a $\phi/6$-expander
decomposition of the graph $G^{(i)}$. Thus it remains to argue about the
correctness of $\mathcal{U}^{\prime}_{(i)}$ and
$\mathcal{U}^{\prime\prime}_{(i)}$.

Let $P_{U}$ be the set of vertices pruned out of a cluster $U$ that the data-
structure $\textsc{DecExpander}(G,\phi)$ returns upon the $i$-th edge
deletion. To prove that the update of $U^{\prime}=\mathrm{trim}(U)$ and
$U^{\prime\prime}=\mathrm{shave}(U^{\prime})$ with respect to $P_{U}$ is
correct, by Definition 4.3, consider the following invariants

  * (1)

for all $u\in U^{\prime}=\mathrm{trim}(U),~{}\deg_{U^{\prime}}(u)\geq
2/5\deg(u)$.

  * (2)

$U^{\prime\prime}=\mathrm{shave}(U^{\prime})=\\{u\in
U^{\prime}\mid\deg_{U^{\prime}}(u)\geq\deg(u)/2+1\\}$.

For every vertex $u\in P_{U}$ with $u\in U^{\prime}$, note that our
subprocedure $\textsc{Remove}(u)$ removed from $U^{\prime}=\mathrm{trim}(U)$
all vertices $v$ for which $\deg_{U^{\prime}}(v)<2/5\deg(v)$, and thus the
invariant (1) holds for the vertices that are left in $U^{\prime}$. Moreover,
as already pointed out in [8], $\mathrm{trim}(U)$ is unique so the order in
which vertices are removed does not matter. Similarly, by construction we have
that subprocedure $\textsc{Remove}(u)$ detects all vertices in
$U^{\prime\prime}=\mathrm{shave}(U^{\prime})$ that do not satisfy invariant
(2). It follows that $U^{\prime}$ and $U^{\prime\prime}$ are maintained
correctly, which in turn implies that $\mathcal{U}^{\prime}_{(i)}$ and
$\mathcal{U}^{\prime\prime}_{(i)}$ are also correct.

The guarantee on the size of the sparsifier follows directly from Lemma 4.1.

We next study the running time of our algorithm.

######  Lemma 4.5 (Running Time)

The decremental algorithm for maintaining a NMC sparsifier runs in
$\tilde{O}(m/\phi)$ total update time.

  * Proof.

The running time of the algorithm is dominated by (1) the time to maintain a
decremental expander decomposition $\mathcal{U}$, (2) the total time to
maintain $\mathcal{U}^{\prime}$ and $\mathcal{U}^{\prime\prime}$ and (3) the
cost of performing vertex uncontractions. By Theorem 4.3, (1) is bounded by
$\tilde{O}(m/\phi)$. To bound (2), we can implement subprocedure
$\textsc{Remove}(u)$ for a vertex $u$ in $O(\deg(u))$ time, excluding the
recursive calls to its neighbours. Since the updates from $G$ and
$\mathcal{U}$ are decremental (as they consist of either edge deletions or
vertex deletions), once a vertex leaves a set $U^{\prime}$ or
$U^{\prime\prime}$, it can never join back. Hence, it follows that (2) is
bounded by $\sum_{u\in V}O(\deg(u))=O(m)$. Similarly, a vertex $u$ can be
uncontracted at most once, and this operation can also be implemented in
$O(\deg(u))$ time, giving a total runtime of $\sum_{u\in V}O(\deg(u))=O(m)$
for (3). Bringing (1), (2) and (3) together proves the claim of the lemma.

####  4.2.2 Extension to Fully Dynamic NMC sparsifier

We follow a widespread approach in data structures for turning a decremental
algorithm into a fully dynamic algorithm and apply it to our problem for
maintaining a NMC sparsifier.

At a high level, our approach uses a decremental algorithm for maintaining a
NMC sparsifier of the graph and handles edge insertions by keeping them “on
the side”. It crucially relies on the fact that adding an edge to the
sparsifier yields a sparsifier for the new graph augmented by that edge. To
make sure that the size of the sparsifier remains small after these edge
augmentations, we restart our decremental algorithm from scratch after the
number of updates exceeds a predefined threshold. This leads to the following
result.

###### Theorem 4.5

Given an unweighted, undirected graph $G=(V,E)$ with $m$ edges and a parameter
$\phi\in(0,1)$ satisfying $\phi\geq c/\delta$ for some positive constant
$c\geq 240$, there is a fully dynamic algorithm that maintains a NMC
sparsifier $H$ of size $\tilde{O}(\phi m)$ in $\tilde{O}(1/\phi^{3})$
amortized time per edge insertion or deletion.

Our data structure subdivides the sequence of edge updates into phases of
length $\phi^{2}m$, where $\phi\in(0,1)$, satisfying $\phi\geq c/\delta$ for
some positive constant $c\geq 240$. Our algorithm maintains

  * •

the set of edges $I$ that represents the edges inserted since the beginning of
a phase that have not been subsequently deleted.

At the beginning of each phase, we initialize (i) the decremental algorithm
DecSparsifier$(G,\phi)$ (Theorem 4.4) to maintain a NMC sparsifier $H$ of the
current graph $G$, and (ii) set $I\leftarrow\emptyset$.

Let $e$ be an edge update to $G$. If $e$ is an edge insertion to $G$, we add
it to the set $I$. If $e$ is deleted from $G$, we consider two cases: If $e\in
I$, we simply delete $e$ from $I$. If $e\not\in I$, we pass the deletion of
$e$ to $\textsc{DecSparsifier}(G,\phi)$ to update the sparsifier $H$. We
maintain $H^{\prime}\leftarrow H\cup I$ as the sparsifier of the current
graph. This completes the description of the algorithm.

We next show that our fully dynamic algorithm maintains a correct NMC
sparsifier at any time.

######  Lemma 4.6 (Correctness)

The fully dynamic algorithm correctly maintains a NMC sparsifier $H^{\prime}$
of size $O(\phi m)$.

  * Proof.

Let $G=(G_{0}\setminus D)\cup I$ be the current graph, where $G_{0}$ is the
graph at the beginning of a phase, $D$ is the set of edges deleted from
$G_{0}$, and $I$ is the of edges inserted since the beginning of a phase that
have not been subsequently deleted. Let $H^{\prime}=H\cup I$ by the sparsifier
our data-structure maintains.

By Theorem 4.5, we know that $H$ is a NMC sparsifier of $G_{0}\setminus D$. We
claim that $H\cup I$ is a NMC sparsifier of $(G_{0}\setminus D)\cup I$. To see
this, consider the case when $I=\\{e\\}$, where $e=(u,v)$. Once proving this
simpler case, our general claim follows follows by induction. As $H$ is a
contraction of $G_{0}\setminus D$ (Lemma 4.1), there is a vertex mapping
$f:V(G_{0}\setminus D)\rightarrow V(H)$ assigning nodes that are contracted
together to a single node in $V(H)$. We distinguish two cases. If $f(u)\neq
f(v)$, then $e$ increases a non-singleton minimum cut in $G_{0}\setminus
D\cup\\{e\\}$ by at most one. Since the edge is present both in
$G_{0}\setminus D\cup\\{e\\}$ and $H\cup\\{e\\}$, it follows $H\cup\\{e\\}$
preserves all non-singleton minimum cuts of $G_{0}\setminus D\cup\\{e\\}$. If
$f(u)=f(v)$, i.e., both endpoints of $e$ are contracted into a single vertex
in $H$, then we claim that $e$ cannot participate in any non-singleton minimum
cut in $G_{0}\setminus D\cup\\{e\\}$. Suppose for contradiction that the
latter holds. Then there exists a non-singleton minimum cut $(C,V\setminus C)$
in $G\setminus D\cup\\{e\\}$ such that

$|E_{G\setminus D\cup\\{e\\}}(C,V\setminus C)|=|E_{G\setminus D}(C,V\setminus
C)|+1,$

where the above equality uses the fact that $e$ is a cut edge. Since a non-
singleton minimum cut $G\setminus D$ can increase by at most $1$ when adding a
single edge, it follows that $(C,V\setminus C)$ is a non-singleton minimum cut
in $G$. Since $H$ is NMC sparsifier of $G$, we have that $(C,V\setminus C)$
must also be non-singleton minimum cut in $H$. Let $s\in V(H)$ be the
supervertex in $H$ containing $u$ and $v$. It follows $\min\\{|s\cap
C|,|s\setminus C|\\}\neq 0$, which contradicts the fact that $H$ is NMC
sparsifier of $G$.

To bound the size of $H^{\prime}$, observe that (1) $H$ is of size $O(\phi m)$
at any time (Theorem 4.4), and (2) $|I|\leq\phi^{2}m$. Therefore, $H^{\prime}$
is of size $O(\phi^{2}m+\phi m)=O(\phi m).$

######  Lemma 4.7 (Running Time)

The fully dynamic algorithm for maintaining a NMC sparsifier runs in
$\tilde{O}(1/\phi^{3})$ amortized time per edge insertion or deletion.

  * Proof.

The total update to maintain a decremental sparsifier is $\tilde{O}(m/\phi)$
(Theorem 4.4) under the condition that the number of deletions is smaller then
$\phi^{2}m$. Our data-structure makes sure that the number of updates within a
phase never exceeds $\phi^{2}m$. Charging the total update time to these
updates, we get an amortized update time of $\tilde{O}(m/\phi\cdot
1/(\phi^{2}m))=O(1/\phi^{3})$.

###  4.3 The Algorithm

In this section we show an algorithm for Theorem 1.2. Our main idea is to run
in “parallel” a variant of the fully algorithm for maintaining a NMC
sparsifier (Theorem 4.5) and the exact fully dynamic edge connectivity
algorithm due to Thorup [56] which is efficient whenever the edge connectivity
is polylogarithmic or a small polynomial in the number of vertices. We also
maintain a carefully chosen threshold edge connectivity value which tells us
when to switch between the two algorithms. We start by observing that the
fully dynamic algorithm for maintaining a NMC sparsifier $H$ of a graph $G$
(Theorem 4.5) gives the following simple algorithm for edge connectivity: (i)
maintain the minimum degree $\delta$ of the current graph $G$, (ii) after each
edge update compute $\lambda(H)$ on the graph $H$ (Theorem 2.1), and (iii) set
the edge connectivity $\lambda(G)$ of the current graph to be
$\min\\{\delta,\lambda(H)\\}$. The following corollary is an immediate
consequence of Theorem 4.5.

###### Corollary 4.1

Given an unweighted, undirected graph $G=(V,E)$ with $m$ edges and a parameter
$\phi\in(0,1)$, there is a fully dynamic algorithm for maintaining an edge
connectivity estimate $\mu(G)$ in $\tilde{O}(1/\phi^{3}+\phi m)$ amortized
time per edge insertion or deletion. If $\phi\geq c/\delta$, for some positive
constant $c\geq 240$, then the edge connectivty estimate is correct, i.e.,
$\mu(G)=\lambda(G)$.

Next we review the result of Thorup [56] concerning efficient maintenance of
small edge connectivity.

######  Theorem 4.6 (Theorem 26, [56])

Given an unweighted, undirected graph $G=(V,E)$ with $n$ edges, and a
parameter $\eta\in(0,n)$, there is a fully dynamic algorithm for maintaining
an edge connectivity estimate $\mu(G)$ in $\tilde{O}(\eta^{7}\sqrt{n})$ worst-
case time per edge insertion or deletion. If $\lambda(G)\leq\eta$, then the
edge connectivity estimate is correct, i.e., $\mu(G)=\lambda(G)$.

We now have all the tools to present our sub-linear fully dynamic edge
connectivity algorithm, which proceeds as follows. Let $\tau=n^{a}$ be a
threshold value on the edge connectivity to be determined shortly, where
$a\in(0,1)$ is a parameter. We run

  * (1) the fully dynamic algorithm $\mathcal{A}_{1}$ from Theorem 4.6 with parameter $\eta=(\tau+1)$, and

  * (2) the fully dynamic algorithm $\mathcal{A}_{2}$ from Corollary 4.1 with parameter $\phi=240/\tau$.

We extend both algorithms $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ to perform a
test on how edge connectivity $\lambda(G)$ of the current graph compares to
the threshold value $\tau$ _after_ the algorithm that is currently being used
to answer queries has processed an edge update. These extensions allow us to
switch between these two algorithms, so the queries we answer regarding
$\lambda(G)$ are correct.

First, observe that both algorithms internally explicitly maintain
$\lambda(G)$. We proceed as follows

  * •

Suppose $\mathcal{A}_{1}$ is currently being used to answer queries. If
$\lambda(G)\leq\tau$ after an update operation operation, then we do not
switch. Otherwise (i.e., $\lambda(G)=(\tau+1)$), we switch to
$\mathcal{A}_{2}$ for the next operation.

  * •

Suppose $\mathcal{A}_{2}$ is currently being used to answer queries. If
$\lambda(G)\geq(\tau+1)$ after an update operation, then we do not switch.
Otherwise (i.e., $\lambda(G)=\tau$), we switch to $\mathcal{A}_{1}$ for the
next operation.

We next prove the correctness. It suffices to verify that our parameter
requirements from Theorem 4.6 and Corollary 4.1 are satisfied whenever we use
one of the algorithms to answer queries. Let $G$ be the current graph. Note
that if $\lambda(G)$ was at most $\tau$ before an update operation, we used
algorithm $\mathcal{A}_{1}$, which works correctly, even then $\lambda(G)$
reaches $\tau+1$ after that operation. If $\lambda(G)$ was at least $\tau+1$
before the operation, we use $\mathcal{A}_{2}$ which works correctly even if
$\lambda(G)$ drops to $\tau$ after the operation as $\tau\leq\lambda(G)$. In
either case we have that $\phi=240/\tau\geq 240/\lambda(G)\geq 240/\delta$.
This completes the correctness proof.

The running time is bounded as follows. By Theorem 4.6 and
$\lambda(G)\leq\tau+1$, (1) supports edge updates in
$\tilde{O}(\tau^{7}\sqrt{n})$ worst-case time. By Corollary 4.1, (2)
guarantees a $\tilde{O}(1/\phi^{3}+\phi m)=\tilde{O}(\tau^{3}+m/\tau)$
amortized time per update. Bringing these running times together, we get that
the amortized time per edge update is

$\tilde{O}(\tau^{7}\sqrt{n}+\tau^{3}+m/\tau)=\tilde{O}(\tau^{7}\sqrt{n}+m/\tau).$

Balancing the two terms in the above expression, we get
$\tau=m^{\nicefrac{{1}}{{8}}}/n^{\nicefrac{{1}}{{16}}}$, which in turn implies
that the amortized update time of our algorithm is
$O(m^{\nicefrac{{7}}{{8}}}n^{1/16})$. This completes the proof of Theorem 1.2.

##  5 Concluding remarks and open problems

We showed two sub-linear algorithms for exactly maintaining edge connectivity
in fully dynamic graphs. The main idea behind both algorithms was to maintain
sparsifiers that preserve non-singleton cuts dynamically, and this was
achieved by leveraging the power of random 2-out contractions and expander
decompositions in the context of edge connectivity.

Our work leaves several natural open problems.

  * (1)

_Can our update time for dynamically maintaining exact edge connectivity be
improved?_ We remark that a closer examination of our result based on expander
decompositions reveals that an improvement to Thorup’s result [56] for bounded
edge connectivity (specifically, improving the polynomial dependency on the
edge connectivity) would immediately lead to an improved running time. It
would be very interesting to investigate whether this can be achieved.

  * (2)

_Is there a fully dynamic algorithm for $(1+\varepsilon)$-approximating edge
connectivity in $\textup{poly}(\log n)\varepsilon^{-O(1)}$ update time?_ The
best known algorithm due to Thorup achieves $\tilde{O}(\sqrt{n})$ update time,
and even going beyond this $\tilde{O}(\sqrt{n})$ barrier remains an important
open problem in dynamic graph algorithms.

## Acknowledgement

_M. Henzinger:_ This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF)
project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N,
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.

## References

  * [1] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 328–338, 2009.
  * [2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Symposium on Discrete Algorithms (SODA), pages 459–467, 2012\.
  * [3] Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup.  Maintaining information in fully dynamic trees with top trees.  ACM Transactions on Algorithms (TALG), 1(2):243–264, 2005.
  * [4] Sepehr Assadi and Aditi Dudeja.  A simple semi-streaming algorithm for global minimum cuts.  In Symposium on Simplicity in Algorithms (SOSA), pages 172–180, 2021.
  * [5] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun.  Fully-dynamic graph sparsifiers against an adaptive adversary.  In International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 20:1–20:20, 2022.
  * [6] Nalin Bhardwaj, Antonio Molina Lovett, and Bryce Sandlund.  A simple algorithm for minimum cuts in near-linear time.  In Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 12:1–12:18, 2020.
  * [7] 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.  In Symposium on Foundations of Computer Science (FOCS), pages 1158–1167, 2020.
  * [8] Julia Chuzhoy and Sanjeev Khanna.  A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.  In Symposium on Theory of Computing (STOC), pages 389–400, 2019\.
  * [9] Graham Cormode and Donatella Firmani.  A unifying framework for $\ell_{0}$-sampling algorithms.  Distributed and Parallel Databases, 32(3):315–335, 2014.
  * [10] Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak.  Distributed edge connectivity in sublinear time.  In Symposium on Theory of Computing (STOC), pages 343–354, 2019\.
  * [11] Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai.  Distributed weighted min-cut in nearly-optimal time.  In Symposium on Theory of Computing (STOC), pages 1144–1153, 2021\.
  * [12] LR Ford and DR Fulkerson.  Flows in networks.  1962\.
  * [13] Greg N Frederickson.  Data structures for on-line updating of minimum spanning trees, with applications.  SIAM Journal on Computing, 14(4):781–798, 1985.
  * [14] Greg N Frederickson.  Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees.  SIAM Journal on Computing, 26(2):484–538, 1997.
  * [15] Harold N. Gabow.  A matroid approach to finding edge connectivity and packing arborescences.  Journal of Computer and System Sciences, 50(2):259–273, 1995.  Announced at STOC’91.
  * [16] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Minimum cut in o(m log2 n) time.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 57:1–57:15, 2020.
  * [17] Paweł Gawrychowski, Shay Mozes, and Oren Weimann.  A note on a recent algorithm for minimum cut.  In Symposium on Simplicity in Algorithms (SOSA), pages 74–79, 2021\.
  * [18] Barbara Geissmann and Lukas Gianinazzi.  Parallel minimum cuts in near-linear work and low depth.  In Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 1–11, 2018.
  * [19] Mohsen Ghaffari and Fabian Kuhn.  Distributed minimum cut approximation.  In International Symposium on Distributed Computing (DISC), pages 1–15, 2013.
  * [20] Mohsen Ghaffari and Krzysztof Nowicki.  Congested clique algorithms for the minimum cut problem.  In Symposium on Principles of Distributed Computing (PODC), pages 357–366, 2018.
  * [21] Mohsen Ghaffari and Krzysztof Nowicki.  Massively parallel algorithms for minimum cut.  In Symposium on Principles of Distributed Computing (PODC), pages 119–128, 2020.
  * [22] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup.  Faster algorithms for edge connectivity via random 2-out contractions.  In Symposium on Discrete Algorithms (SODA), pages 1260–1279, 2020\.
  * [23] Ralph E Gomory and Tien Chung Hu.  Multi-terminal network flows.  Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
  * [24] Gramoz Goranci, Monika Henzinger, and Mikkel Thorup.  Incremental exact min-cut in polylogarithmic amortized update time.  ACM Transactions on Algorithms (TALG), 14(2):1–21, 2018.
  * [25] Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan.  The expander hierarchy and its applications to dynamic graph algorithms.  In Symposium on Discrete Algorithms (SODA), pages 2212–2228, 2021\.
  * [26] Jianxiu Hao and James B. Orlin.  A faster algorithm for finding the minimum cut in a directed graph.  J. Algorithms, 17(3):424–446, 1994.
  * [27] Monika Henzinger, Satish Rao, and Di Wang.  Local flow partitioning for faster edge connectivity.  SIAM J. Comput., 49(1):1–36, 2020.
  * [28] Monika R Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  Journal of the ACM (JACM), 46(4):502–516, 1999.
  * [29] Monika Rauch Henzinger.  A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity.  J. Algorithms, 24(1):194–220, 1997.
  * [30] Monika Rauch Henzinger and Valerie King.  Fully dynamic 2-edge connectivity algorithm in polylogarithmic time per operation.  SRC Technical Note, 4, 1997.
  * [31] Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  Journal of the ACM (JACM), 48(4):723–760, 2001.
  * [32] Jacob Holm, Eva Rotenberg, and Mikkel Thorup.  Dynamic bridge-finding in o (log2 n) amortized time.  In Symposium on Discrete Algorithms (SODA), pages 35–52. SIAM, 2018\.
  * [33] Bruce M Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Symposium on Discrete algorithms (SODA), pages 1131–1142, 2013\.
  * [34] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In Symposium on Discrete Algorithms (SODA), pages 21–30, 1993.
  * [35] David R. Karger.  Using randomized sparsification to approximate minimum cuts.  In Symposium on Discrete Algorithms (SODA), pages 424–432, 1994\.
  * [36] David R. Karger.  Minimum cuts in near-linear time.  Journal of the ACM, 47(1):46–76, 2000.  Announced at STOC’96.
  * [37] David R. Karger and Clifford Stein.  A new approach to the minimum cut problem.  J. ACM, 43(4):601–640, 1996.
  * [38] Ken-ichi Kawarabayashi and Mikkel Thorup.  Deterministic edge connectivity in near-linear time.  J. ACM, 66(1):4:1–4:50, 2019.  Announced at STOC’15.
  * [39] Jakub Lacki and Piotr Sankowski.  Min-cuts and shortest cycles in planar graphs in o (n loglogn) time.  In European Symposium on Algorithms, pages 155–166. Springer, 2011\.
  * [40] Troy Lee, Tongyang Li, Miklos Santha, and Shengyu Zhang.  On the cut dimension of a graph.  arXiv preprint arXiv:2011.05085, 2020.
  * [41] Jason Li.  Deterministic mincut in almost-linear time.  In Symposium on Theory of Computing (STOC), pages 384–395, 2021\.
  * [42] Jason Li and Debmalya Panigrahi.  Deterministic min-cut in poly-logarithmic max-flows.  In Symposium on Foundations of Computer Science (FOCS), pages 85–92, 2020.
  * [43] Andrés López-Martínez, Sagnik Mukhopadhyay, and Danupon Nanongkai.  Work-optimal parallel minimum cuts for non-sparse graphs.  arXiv preprint arXiv:2102.06565, 2021.
  * [44] Sagnik Mukhopadhyay and Danupon Nanongkai.  Weighted min-cut: sequential, cut-query, and streaming algorithms.  In Symposium on Theory of Computing (STOC), pages 496–509, 2020\.
  * [45] Hiroshi Nagamochi and Toshihide Ibaraki.  Computing edge-connectivity in multigraphs and capacitated graphs.  SIAM J. Discret. Math., 5(1):54–66, 1992.
  * [46] Hiroshi Nagamochi and Toshihide Ibaraki.  A linear-time algorithm for finding a sparse k-connected spanning subgraph of ak-connected graph.  Algorithmica, 7(1):583–596, 1992.
  * [47] Danupon Nanongkai and Thatchaphol Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o (n1/2-$\varepsilon$)-time.  In Symposium on Theory of Computing (STOC), pages 1122–1129, 2017\.
  * [48] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In Symposium on Foundations of Computer Science (FOCS), pages 950–961, 2017.
  * [49] Danupon Nanongkai and Hsin-Hao Su.  Almost-tight distributed minimum cut algorithms.  In International Symposium on Distributed Computing (DISC), pages 439–453, 2014.
  * [50] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  arXiv preprint arXiv:1908.03022, 2019.
  * [51] David Pritchard and Ramakrishna Thurimella.  Fast computation of small cuts via cycle space sampling.  ACM Transactions on Algorithms (TALG), 7(4):1–30, 2011.
  * [52] Aviad Rubinstein, Tselil Schramm, and S Matthew Weinberg.  Computing exact minimum cuts without knowing the graph.  arXiv preprint arXiv:1711.03165, 2017.
  * [53] Thatchaphol Saranurak.  A simple deterministic algorithm for edge connectivity.  In Symposium on Simplicity in Algorithms (SOSA), pages 80–85, 2021\.
  * [54] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: Faster, stronger, and simpler.  In Symposium on Discrete Algorithms (SODA), pages 2616–2635, 2019\.
  * [55] Mechthild Stoer and Frank Wagner.  A simple min-cut algorithm.  J. ACM, 44(4):585–591, 1997.
  * [56] Mikkel Thorup.  Fully-dynamic min-cut.  Combinatorica, 27(1):91–127, 2007.
  * [57] Mikkel Thorup and David R Karger.  Dynamic graph algorithms with applications.  In Scandinavian Workshop on Algorithm Theory (SWAT), pages 1–9. Springer, 2000.