Incremental Exact Min-Cut in Poly-logarithmic
Amortized Update Time

arXiv:1611.06500v1 [] 20 Nov 2016

Gramoz Goranci∗

Monika Henzinger†

Mikkel Thorup‡

Abstract
We present a deterministic incremental algorithm for exactly maintaining the size of a minie
mum cut with O(1)
amortized time per edge insertion and O(1) query time. This result partially
answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast
to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem.
Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and
Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997].
We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(n log n/ε2 ) space Monte-Carlo algorithm that can process
a stream of edge insertions starting from an empty graph, and with high probability, the algoe
rithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O(1)
amortized
update-time and constant query-time.

∗

University of Vienna, Faculty of Computer Science, Vienna, Austria. E-mail: gramoz.goranci@univie.ac.at
University of Vienna, Faculty of Computer Science, Vienna, Austria. E-mail: monika.henzinger@univie.ac.at
‡
Faculty of Computer Science, University of Copenhagen, Denmark. E-mail: mikkel2thorup@gmail.com

†

1

Introduction

Computing a minimum cut of a graph is a fundamental algorithmic graph problem. While most of
the focus has been on designing static efficient algorithms for finding a minimum cut, the dynamic
maintenance of a minimum cut has also attracted increasing attention over the last two decades.
The motivation for studying the dynamic setting is apparent, as real-life networks such as social or
road network undergo constant and rapid changes.
Given an initial graph G, the goal of a dynamic graph algorithm is to build a data-structure
that maintains G and supports update and query operations. Depending on the types of update
operations we allow, dynamic algorithms are classified into three main categories: (i) fully dynamic,
if update operations consist of both edge insertions and deletions, (ii) incremental, if update operations consist of edge insertions only and (iii) decremental, if update operations consist of edge
deletions only. In this paper, we study incremental algorithms for maintaining the size of a minimum cut of an unweighted, undirected graph (denoted by λ(G) = λ) supporting the following
operations:
• Insert(u, v): Insert the edge (u, v) in G.
• QuerySize: Return the exact (approximate) size of a minimum cut of the current G.
For any α ≥ 1, we say that an algorithm is an α-approximation of λ if QuerySize returns a positive
number k such that λ ≤ k ≤ α · λ. Our problem is characterized by two time measures; query time,
which denotes the time needed to answer each query and total update time, which denotes the time
needed to process all edge insertions. We say that an algorithm has an O(t(n)) amortized update
time if it takes O(m(t(n))) total update time for m edge insertions starting from an empty graph.
e to hide poly-logarithmic factors.
We use O(·)

Related Work. For over a decade, the best known static and deterministic algorithm for computing a minimum cut was due to Gabow [10] which runs in O(m + λ2 log n) time. Recently,
e
Kawarabayashi and Thorup [19] devised a O(m)
time algorithm which applies only to simple, unweighted and undirected graphs. Randomized Monte Carlo algorithms in the context of static
minimum cut were initiated by Karger [17]. The best known randomized algorithm is due to
Karger [18] and runs in O(m log3 n) time.
Karger [16] was the first to study the dynamic maintenance of a minimum cut in its
pfull generality. He devised a fully dynamic, albeit randomized, algorithm for maintaining a 1 + 2/εe 1/2+ε ) expected amortized time per edge operation. In
approximation of the minimum cut in O(n
the incremental setting, he showed that the update time for the same approximation ratio can
e ε ). Thorup and Karger [29] improved upon the above guarantees by
be further improved to O(n
p
e
expected amortized time per edge
achieving an approximation factor of 2 + o(1) and an O(1)
operation.
Henzinger [14] obtained the following guarantees for the incremental minimum cut; for any
ε ∈ (0, 1], (i) an O(1/ε2 ) amortized update-time for a (2 + ε)-approximation, (ii) an O(log3 n/ε2 )
expected amortized update-time for a (1 + ε)-approximation and (iii) an O(λ log n) amortized
update-time for the exact minimum cut.
For minimum cut up to some poly-logarithmic size, Thorup [28] gave a fully dynamic Montee √n) time per edge operation. He also
Carlo algorithm for maintaining exact minimum cut in O(
showed how to obtain an 1 + o(1)-approximation of an arbitrary sized minimum cut with the same
time bounds. In comparison to previous results, it is worth pointing out that his work achieves
worst-case update times.
1

Lacki and Sankowski [21] studied the dynamic maintenance of the exact size of the minimum
cut in planar graphs with arbitrary edge weights. They obtained a fully dynamic algorithm with
e 5/6 ) worst-case query and update time.
O(n
There has been a growing interest in proving conditional lower bounds for dynamic problems
in the last few years [1, 13]. A recent result of Nanongkai and Saranurak [25] shows the following
conditional lower-bound for the exact weighted minimum cut assuming the Online Matrix-Vector
Multiplication conjecture: for any ε > 0, there are no fully-dynamic algorithms with polynomialtime preprocessing that can simultaneously achieve O(n1−ε ) update-time and O(n2−ε ) query-time.
Our Results and Technical Overview. We present two new incremental algorithms concerning
the maintenance of the size of a minimum cut. Both algorithms apply to undirected, unweighted
graphs. Our first and main result, presented in Section 4, shows that there is a deterministic
e
incremental algorithm for exactly maintaining the size of a minimum cut with O(1)
amortized time
per operation and O(1) query time. This result allows us to partially answer in the affirmative
a question regarding efficient dynamic algorithms for exact minimum cut posed by Thorup [28].
Additionally, it also stays in sharp contrast to the polynomial conditional lower-bound for the
fully-dynamic weighted minimum cut problem of [25].
We obtain our result by heavily relying on a recent sparsification technique developed in the
context of static minimum cut algorithms. Specifically, for a given simple graph G, Kawarabayashi
e
and Thorup [19] designed an O(m)
procedure that contracts vertex sets of G and produces a
multigraph H with considerably fewer vertices and edges while preserving some family of cuts of
size up to (3/2)λ(G). Motivated by the properties of H, we crucially observe that it is “safe” to
work entirely with graph H as long as the sequence of newly inserted edges do not increase the
size of the minimum cut in H by more than (3/2)λ(G). If the latter occurs, we recompute a new
multigraph H for the current graph G. Since λ(G) ≤ n, the number of such re-computations is
O(log n). For maintaining the minimum-cut of H, we appeal to the exact incremental algorithm
due to Henzinger [14]. Though the combination of this two algorithms might seem immediate at
first sight, it is not alone sufficient for achieving the claimed bounds. Our main contribution is to
overcome some technical obstacles and formally argue that such combination indeed leads to our
desirable guarantees.
Motivated by the recent work on space-efficient dynamic algorithms [5, 12], we also study the
e
efficient maintenance of the size of a minimum cut using only O(n)
space. Concretely, we present
2
a O(n log n/ε ) space Monte-Carlo algorithm that can process a stream of edge insertions starting
from an empty graph, and with high probability, it maintains an (1 + ε)-approximation to the
minimum cut in O(α(n) log 3 n/ε2 ) amortized update-time and constant query-time. Note that
none of the existing streaming algorithms for (1 + ε)-approximate minimum cut [2, 20, 3] achieves
these update and query times.

2

Preliminary

Let G = (V, E) be an undirected, unweighted multi-graph with no self-loops. Two vertices x and y
are k-edge connected if there exist k edge-disjoint paths connecting x and y. A graph G is k-edge
connected if every pair of vertices is k-edge connected. The local edge connectivity λ(G, x, y) of
vertices x and y is the largest k such that x and y are k-edge connected in G. The edge connectivity
λ(G) of G is the largest k such that G is k-edge connected.
For a subset S ⊆ V in G, the edge cut EG (S, V \ S) is a set of edges that have one endpoint
in S and the other in V \ S. We may omit the subscript when clear from the context. Let
2

λ(S, G) = |EG (S, V \ S)| be the size of the edge cut. If S is a singleton, we refer to such cut as a
trivial cut. Two vertices x and y are separated by E(S, V \ S) if they do not belong to the same
connected component induced by the edge cut. A minimum edge cut of x and y is a cut of minimum
size among all cuts separating x and y. A global minimum cut λ(G) for G is the minimum edge
cut over all pairs of vertices. By Menger’s Theorem [22], (a) the size of the minimum edge cut
separating x and y is λ(x, y, G), and (b) the size of the global minimum cut is equal to λ(G).
Let n, m0 and m1 be the number of vertices, initial edges and inserted edges, respectively.
The total number of edges m is the sum of the initial and inserted edges. Moreover, let λ and δ
denote the size of the global minimum cut and the minimum degree in the final graph, respectively.
Note that the minimum degree is always an upper bound on the edge connectivity, i.e., λ ≤ δ and
m = m0 + m1 = Ω(δn).
A subset U ⊆ V is contracted if all vertices in U are identified with some element of U and all
edges between them are discarded. For G = (V, E) and a collection of vertex sets, let H = (VH , EH )
denote the graph obtained by contracting such vertex sets. Such contractions are associated with
a mapping h : V → VH . For an edge subset N ⊆ E, let Nh = {(h(a), h(b)) : (a, b) ∈ N } ⊆ EH be
its corresponding edge subset induced by h.

3

Sparse certificates

In this section we review a useful sparsification tool, introduced by Nagamochi and Ibaraki [23].
Definition 3.1 ([4]). A sparse k-connectivity certificate, or simply a k-certificate, for an unweighted graph G with n vertices is a subgraph G′ of G such that
1. G′ consists of at most k(n − 1) edges, and
2. G′ contains all edges crossing cuts of size at most k.
Given an undirected graph G = (V, E), a maximal spanning forest decomposition (msfd) F of
order k is a decomposition of G into k edge-disjoint spanning forests Fi , S
1 ≤ i ≤ k, such that Fi is
a maximal spanning forest of G \ (F1 ∪ F2 . . . ∪ Fi−1 ). Note that Gk = (V, i≤k Fi ) is a k-certificate.
An msfd fulfills the following property whose proof we defer to the appendix.
Lemma 3.2 ([24]). Let F = (F1 , . . . , Fm ) be an msfd of order m of a graph G = (V, E), and let k
be an integer with 1 ≤ k ≤ m. Then for any nonempty and proper subset S ⊂ V ,
(
≥ k,
if λ(S, G) ≥ k
λ(S, Gk )
= λ(S, G) if λ(S, G) ≤ k − 1.

As Gk is a subgraph of G, λ(Gk ) ≤ λ(G). This implies that λ(Gk ) = min(k, λ(G)).
Nagamochi and Ibaraki [23] presented an O(m + n) time algorithm to construct a special msfd,
which we refer to as DA-msfd.

4

Incremental Exact Minimum Cut

In this section we present a deterministic incremental algorithm that exactly maintains λ(G). The
e
algorithm has an O(1)
update-time, an O(1) query time and it applies to any undirected, unweighted
graph G = (V, E). The result is obtained by carefully combining a recent result of Kawarabayashi
and Thorup [19] on static min-cut and the incremental exact min-cut algorithm of Henzinger [14].
We start by describing the maintenance of non-trivial cuts, that is, cuts with at least two vertices
on both sides.
3

Maintaining non-trivial cuts. Kawarabayashi and Thorup [19] devised a near-linear time algorithm that contracts vertex sets of a simple input graph G and produces a sparse multi-graph
preserving all non-trivial minimum cuts of G. In the following theorem, we state a slightly generalized version of this algorithm.
Theorem 4.1 (KT-Sparsifier [19]). Given an undirected, unweighted graph G with n vertices,
e
m edges, and min-cut λ, in O(m)
time, we can contract vertex sets and produce a multigraph H
e
e
which consists of only mH = O(m/λ) edges and nH = O(n/λ)
vertices, and which preserves all
non-trivial minimum cuts along with the non-trivial cuts of size up to (3/2)λ in G.

As far as non-trivial cuts are concerned, the above theorem implies that it is safe work on H
instead of G as long as the sequence of newly inserted edges satisfies λH ≤ (3/2)λ. To incrementally
maintain the correct λH , we apply Henzinger’s algorithm [14] on top of H. The basic idea to verify
the correctness of the solution is to compute and store all min-cuts of H. Clearly, a solution is
correct as long as an edge insertion does not increase the size of all min-cuts. If all min-cuts have
increased, a new solution is computed using information about the previous solution. We next show
how to do this efficiently.
To store all minimum edge cuts we use the cactus tree representation by Dinitz, Karzanov and
Lomonosov [7]. A cactus tree of a graph G = (V, E) is a weighted graph Gc = (Vc , Ec ) defined as
follows: There is a mapping φ : V → Vc such that:
1. Every node in V maps to exactly one node in Vc and every node in Vc corresponds to a
(possibly empty) subset of V .
2. φ(x) = φ(y) iff x and y are (λ(G) + 1)-edge connected.
3. Every minimum cut in Gc corresponds to a min-cut in G, and every min-cut in G corresponds
to at least one min-cut in Gc .
4. If λ is odd, every edge of Ec has weight λ and Gc is a tree. If λ is even, Gc consists of paths
and simple cycles sharing at most one vertex, where edges that belong to a cycle have weight
λ/2 while those not belonging to a cycle have weight λ.
Dinitz and Westbrook [8] showed that given a cactus tree, we can use the data structures from [11,
26] to maintain the cactus tree for minimum cut size λ under u insertions, reporting when the
minimum cut size increases to λ + 1 in O(u + n) total time.
To quickly compute and update the cactus tree representation of a given multigraph G, we use
an algorithm due to Gabow [9]. The algorithm computes first a subgraph of G, called a complete
λ-intersection or I(G, λ), with at most λn edges, and uses I(G, λ) to compute the cactus tree.
Given some initial graph with m0 edges, the algorithm computes I(G, λ) and the cactus tree in
e 0 + λ2 n) time. Moreover, given I(G, λ) and a sequence of edge insertions that increase the
O(m
e ′ ), where m′
minimum cut by 1, the new I(G, λ) and the new cactus tree can be computed in O(m
is the number of edges in the current graph (this corresponds to one execution of the Round Robin
subroutine [10]).
Maintaining trivial cuts. We remark that the multigraph H from Theorem 4.1 preserves only
non-trivial cuts of G. If λ = δ, then we also need a way to keep track of a trivial minimum cut.
We achieve this by maintaining a minimum heap HG on the vertices, where each vertex is stored
with its degree. If an edge insertion is performed, the values of the edge endpoints are updated
accordingly in the heap. It is well known that constructing HG takes O(n) time. The supported
4

operations Min(HG ) and UpdateEndpoints(HG,e) can be implemented in O(1) and O(log n)
time, respectively (see [6]).
This leads to Algorithm 1.
Correctness. Let G be the current graph throughout the execution of the algorithm and let H be
the corresponding multigraph maintained by the algorithm. Recall that H preserves some family
of cuts from G. We say that H is correct if and only if there exists a minimum cut from G that is
contained in the union of (a) all trivial cuts of G and (b) all cuts in H. Note that we consider H to
be correct even in the Special Step (i.e., when λH > (3/2)λ∗ ), where H is not updated anymore
since we are certain that the smallest trivial cut is smaller than any cut in H.
To prove the correctness of the algorithm we will show that (1) it correctly maintains a trivial
min-cut at any time, (2) H is correct as long as min{Min(HG ), λH } ≤ (3/2)λ∗ (and when this
condition fails we rebuild H), and (3) as long as λH ≤ (3/2)λ∗ , the algorithm correctly maintains
all cuts of size up to λH + 1 of H.
Let Nh be the set of recently inserted edges in H that the algorithm maintains during the
execution of the while loop in Step 2.
Lemma 4.2. Let H = (VH , EH ) be a multigraph with minimum cut λH and let Nh be a set
with Nh ⊆ EH . Further, let F1 , . . . , Fm beSa DA-msfd of order m ≥ λH + 1 of H \ Nh , and let
H ′ = (VH , E ′ ) be a graph with E ′ = Nh ∪ i≤λH +1 Fi . Then, a cut is a min-cut in H ′ iff it is a
min-cut in H.
Proof. We first show that every non-min cut in H is a non-min cut in H ′ . By contrapositive, we
get that a min-cut in H ′ is a min-cut in H.
To this end, let (S, VH \ S) be a cut with |EH (S, VH \ S)| ≥ λH + 1 in H. Define EH (S, VH \ S) ∩
and
Nh = SNh and EH (S, VH \ S) ∩ (EH \ Nh ) = SH\N
h
S h such that EH (S, VH \ S) = SNh ⊎ SH\N
′
and
|EH (S, VH \ S)| = |SNh | + |SH\Nh |. Letting F ′ = i≤λH +1 Fi , we similarly define edge sets SN
h
′
′
′
SF ′ partitioning the edges E (S, VH \ S) that cross the cut (S, VH \ S) in H . First, observe that
′
since edges of Nh are always included in H ′ . In addition, by Lemma 3.2, we know that
S Nh = S N
h
F ′ preserves all cuts of H \ Nh up to size λH + 1. Thus, if |SH\Nh | ≤ λH + 1 (Case 1), we get that
′ |+|S ′ | = |S
|SH\Nh | = |SF′ ′ |. It follows that |E ′ (S, VH \S)| = |SN
Nh |+|SH\Nh | = |EH (S, VH \S)| ≥
F′
h
′
λH + 1. If |SH\Nh | > λH + 1 (Case 2), then F must contain at least λH + 1 edges crossing such cut
′ | + |S ′ | ≥ λ + 1. In both
and thus |SF′ ′ | ≥ λH + 1. The latter implies that |E ′ (S, VH \ S)| = |SN
H
F′
h
′
′
cases, H being a subgraph of H implies that λ(H ) ≤ λH . Thus (S, VH \ S) cannot be a min-cut
in H ′ .
For the other direction, consider a min-cut (D, VH \ D) of size |E ′ (D, VH \ D)| in H ′ . Let
′
be defined as above. Considering the cut (D, VH \ D) in H, we know that
DNh , DH\Nh , DF′ ′ , DN
h
′
since edges of Nh
|EH (D, VH \ D)| = |DNh | + |DH\Nh | ≥ λH . We first note that DNh = DN
h
′
are always included in H . Then, similarly as above, by Lemma 3.2 we know that if |DH\Nh | ≤
′ | + |D ′ | = |D
λH + 1, then |E ′ (D, VH \ D)| = |DN
Nh | + |DH\Nh | = |EH (D, VH \ D)| ≥ λH .
F′
h
′
If |DH\NH | > λH + 1, then F must contain at least λH + 1 edges crossing such cut and thus
|E ′ (D, VH \ D)| ≥ λH + 1. Combining both bounds we obtain that |E ′ (D, VH \ D)| ≥ λH . Since
(D, VH \ D) was chosen arbitrarily, we get that λ(H ′ ) ≥ λH must hold. The latter along with
λ(H ′ ) ≤ λH imply that λ(H ′ ) = λH .
Lemma 4.3. The algorithm correctly maintains a trivial min-cut in G.
Proof. This follows directly from the min-heap property of HG .

5

Algorithm 1 Incremental Exact Minimum Cut
1: Compute the size λ0 of the min-cut of G and set λ∗ = λ0 .
Build a heap HG on the vertices, where each vertex stores its degree as a key.
Compute a multigraph H by running KT-sparsifier on G and a mapping h : V → VH .
Compute the size λH of the min-cut
of H, a DA-msfd F1 , . . . , Fm of order m of H,
S
I(H, λH ), and a cactus-tree of i≤λH +1 Fi .
2: Set Nh = ∅.
while there is at least one minimum cut of size λH do
Receive the next operation.
if it is a query then return min{λH , Min(HG )}
else it is the insertion of an edge (u, v), then
update the cactus tree according to the insertion of the new edge (h(u), h(v)),
add the edge (h(u), h(v)) to Nh and update the degrees of u and v in HG .
endif
endwhile
Set λH = λH + 1.
3: if min{λH , Min(HG )}> (3/2)λ∗ then
// Full Rebuild Step
Compute λ(G) and set λ∗ = λ(G).
Compute a multigraph H by running KT-sparsifier on the current graph G.
Update λH to be the min-cut of H, compute
a DA-msfd F1 , . . . , Fm of order m of H,
S
and then I(H, λH ) and a cactus tree of i≤λH +1 Fi .
else if λH ≤ (3/2)λ∗ then
// Partial Rebuild Step
S
Compute a DA-msfd F1 , . . . , Fm of order m of i≤λH +1 Fi ∪ Nh and
call the resulting forests F1 , . . . , Fm .
S
Let H ′ = (VH , E ′ ) be a graph with E ′ = I(H, λH − 1) ∪ i≤λH +1 Fi .
Compute I(H ′ , λH ) and a cactus tree of H ′ .
else // Special Step
while Min(HG ) ≤ (3/2)λ∗ do
if the next operation is a query then return Min(HG )
else update the degrees of the edge endpoints in HG .
endif
endwhile
Goto 3.
endif
endif
Goto 2.

6

To simplify our notation, in the following we will refer to Step 1 as a Full Rebuild Step
(namely the initial Full Rebuild Step).
Lemma 4.4. For some current graph G, let H be the maintained multi-graph of G under the vertex
mapping h and assume that λH ≤ (3/2)λ∗ , where λ∗ denotes the min-cut of G at the last Full
Rebuild Step. Then the algorithm correctly maintains λH = λ(H).
Proof. At the time of the last Full Rebuild Step, the algorithm calls KT-sparsifier on G, which
yields a multigraph H that preserves all non-trivial min-cuts of G. The value of λH is updated to
λ(H) and a DA-msfd and a cactus tree are constructed for H. The latter preserve all cuts of H of
size up to λH + 1. Thus, the value of λH is correct at this step.
Now suppose that the graph after the last Full Rebuild Step has undergone a sequence of
edge insertions, which resulted in the current graph G and its corresponding multigraph H under
the vertex mapping h. During these insertions, as long as λH ≤ (3/2)λ∗ , a sequence of k Partial
(i)
Rebuild Steps is executed, for some k ≥ 1. Let λH be the value of λH after the i-th execution
(k)
(k)
of Partial Rebuild Step, where 1 ≤ i ≤ k. Since, λH = λ(H), it suffices to show that λH is
correct. We proceed by induction.
(1)
For the base case, we show that λH is correct. First, using the fact that λH and the cactus tree
are correct at the last Full Rebuild Step and that the incremental cactus tree algorithm correctly
tell us when to increment λH , we conclude that incrementing the value of λH in Step 2 is valid.
(1)
Thus, λH is correct. Next, in a Partial Rebuild Step, the algorithm sparsifies the graph while
(1)
preserving all cuts of size up to λH + 1 and producing a new cactus tree for the next insertions.
The correctness of the sparsification follows from Lemma 4.2.
(k−1)
is correct. Then, similarly to the base case, the
For the induction step, let us assume that λH
(k−1)
correctness of λH , the cactus tree from the (k−1)-st Partial Rebuild Step and the correctness
(k−1)
in Step 2 is valid
of the incremental cactus tree algorithm give that incrementing the value of λH
(k)
and yields a correct λH .
Note that when λH > (3/2)λ∗ , the above lemma is not guaranteed to hold as the algorithm
does not execute a Partial Rebuild Step in this case. However, we will show below that this
is not necessary for the correctness of the algorithm. The fact that we do not need to execute a
Partial Rebuild Step in this setting is crucial for achieving our time bound.
Lemma 4.5. If min{Min(HG ), λH } ≤ 3/2λ∗ , then H is correct.
Proof. Let (S ′ , V \S ′ ) be any non-trivial cut in G that is not in H. Such a cut must have cardinality
strictly greater than (3/2)λ∗ since otherwise it would be contained in H. We show that (S ′ , V \ S ′ )
cannot be a minimum cut as long as min{Min(HG ), λH } ≤ (3/2)λ∗ holds. We distinguish two
cases.
1. If λH ≤ (3/2)λ∗ , then by Lemma 4.4 the algorithm maintains λH correctly. Since H is
obtained from G by contracting vertex sets, there is a cut (S, VH , S) in H, and thus in G, of
value λH . It follows that (S ′ , V \ S ′ ) cannot be a minimum cut of G since |E(S ′ , V \ S ′ )| >
(3/2)λ∗ ≥ λH = λ(H) ≥ λ(G), where the last inequality follows from the fact that H is a
contraction of G.
2. If Min(HG ) ≤ (3/2)λ∗ , then by Lemma 4.3 there is a cut of size Min(HG ) = δ in G. Similarly,
(S ′ , V \ S ′ ) cannot be a minimum cut of G since |E(S ′ , V \ S ′ )| > (3/2)λ∗ ≥ δ ≥ λ(G).
7

Appealing to the above cases, we conclude H is correct since a min-cut of G is either contained in
H or it is a trivial cut of G.
Lemma 4.6. Let G be some current graph. Then the algorithm correctly maintains λ(G).
Proof. Let G be some current graph and H be the maintained multi-graph of G under the vertex
mapping h. We will argue that λ(G) = min{Min(HG ), λH }.
If min{Min(HG ), λH } ≤ (3/2)λ∗ , then by Lemma 4.5, H is correct i.e., there exists a minimum
cut of G that is contained in the union of all trivial cuts of G and all cuts in H. Lemma 4.3
guarantees that the algorithm correctly maintains Min(HG ), i.e., the trivial minimum cut of G. If
λH ≤ (3/2)λ∗ , then Lemma 4.4 ensures that λH = λ(H), and thus min{Min(HG ), λH } = λ(G). If,
however, λH > (3/2)λ∗ but min{Min(HG ), λH } ≤ (3/2)λ∗ , then λH > min{Min(HG ), λH } which
implies that min{Min(HG ), λH } = Min(HG ) = λ(G). As we argued above, the algorithm correctly
maintains Min(HG ) at any time. Thus it follows that the algorithm correctly maintains λ(G) in
this case as well.
The only case that remains to consider is Min(HG ) > (3/2)λ∗ and λH > (3/2)λ∗ . But this
implies that min{Min(HG ), λH } > (3/2)λ∗ , and the algorithm computes a H and λ(G) from scratch
and sets λH correctly. After this full rebuild λ(G) = min{Min(HG ), λH } trivially holds.
Running Time Analysis.
Theorem 4.7. Let G be a simple graph with n nodes and m0 edges. Then the total time for
e 0 + m1 ). If we start with
inserting m1 edges and maintaining a minimum edge cut of G is O(m
e
an empty graph, the amortized time per edge insertion is O(1).
The size of a minimum cut can be
answered in constant time.

e 0)
Proof. We first analyse Step 1. Building the heap HG and computing λ0 take O(n) and O(m
time, respectively. The total running time for constructing H, I(H, λH ) and the cactus tree is
e 0 ). Thus, the total time for Step 1 is O(m
e 0 ).
e 0 + λ2 · (n/λ0 )) = O(m
dominated by O(m
0
f
0
Let λH , . . . , λH be the values that λH assumes in Step 2 during the execution of the algorithm
in increasing order. We define Phase i to be all steps executed after Step 1 while λH = λiH ,
excluding Full Rebuild Steps and Special Steps. Additionally, let λ∗0 , . . . , λ∗O(log n) be the values
that λ∗ assumes during the algorithm. We define Superphase j to consist of the j-th Full Rebuild
Step along with all steps executed while min{Min(HG ), λH } ≤ (3/2)λ∗j , where λ∗j is the value of
λ(G) at the Full Rebuild Step. Note that a superphase consists of a sequence of phases and
potentially a final Special Step. Moreover, the algorithm runs a phase if λH ≤ (3/2)λ∗ .
We say that λiH belongs to superphase j, if the i-th phase is executed during superphase j and
i
λH ≤ (3/2)λ∗j . We remark that the number of vertices in H changes only at the beginning of a
superphase, and remains unchanged during its lifespan.
Let nj denote the number of vertices in some superphase j. We bound this quantity as follows:
Fact 4.8. Let j be a superphase during the execution of the algorithm. Then, we have
i
i
e
nj = O(n/λ
H ), for all λH belonging to superphase j.

∗ ). Moreover, observe that λ∗ ≤ λi and a phase
e
Proof. From Step 3 we know that nj = O(n/λ
j
j
H
i
∗
is executed whenever λH ≤ (3/2)λj . Thus, for all λiH ’s belonging to superphase j, we get the
following relation
λ∗j ≤ λiH ≤ (3/2)λ∗j ,
(1)
∗ ) = O(n/λ
i ).
e
e
which in turn implies that nj = O(n/λ
j
H

8

For the remaining steps, we divide the running time analysis into two parts (one part corresponding to phases, and the other to superphases).
Part 1. For some superphase j, the i-th phase consists of the i-th execution of a Partial Rebuild
Step followed by the execution of Step 2. Let ui be the number of edge insertions S
in Phase i. The
e
total time for Step 2 is O(nj + ui log n) = O(n + ui ). Using Fact 9, we observe that i≤λH +1 Fi ∪ Nh
e i−1 + n). Thus, the total time for computing DA-msfd in a Partial
has size O(ui−1 + λiH nj ) = O(u
e i−1 + n). Similarly, since H ′ has O(λi nj ) = O(n)
e
e
Rebuild Step is O(u
edges, it takes O(n)
time
H
′
i
to compute I(H , λH ) and the new cactus tree.
e i−1 +ui +n). Let λ and λH denote the size of the minimum
The total time spent in Phase i is O(u
P
cut in the final graph and its corresponding multigraph, respectively. Note that λi=1 ui ≤ m1 ,
λn ≤ m0 + m1 and recall Eqn. (1). This gives that the total work over all phases is
λH
X
i=1

e (ui−1 + ui + n) =
O

λ
X
i=1

e (ui−1 + ui + n) = O(m
e 0 + m1 ).
O

Part 2. The j-th superphase consists of the j-th execution of a Full Rebuild Step along with
a possible execution of a Special Step, depending on whether the condition is met. In a Full
Rebuild Step, the total running time for constructing H, I(H, λ∗j ) and the cactus tree is dominated
e 0 + m1 + (λ∗ )2 · (n/λ∗ )) = O(m
e 0 + m1 ). The running time of a Special Step is O(m
e 1 ).
by O(m
j
j
Throughout its execution, the algorithm begins a new superphase whenever λ(G) = min
{Min(HG ), λH } > (3/2)λ∗ . This implies that λ(G) must be at least (3/2)λ∗ , where λ∗ is the
value of λ(G) at the last Full Rebuild Step. Thus, a new superphase begins whenever λ(G) has
increased by a factor of 3/2, i.e., only O(log n) times over all insertions. This gives that the total
e 0 + m1 ).
time over all superphases is O(m

5

e
Incremental (1 + ε) Minimum Cut with O(n)
space

e
In this section we present two O(n)
space incremental Monte-Carlo algorithms that w.h.p maintain
e
e
the size of a min-cut up to a (1 + ε)-factor. Both algorithms have O(1)
update-time and O(1),
2
2
resp. O(1) query-time. The first algorithm uses O(n log n/ε ) space, while the second one improves
the space complexity to O(n log n/ε2 ).

5.1

An O(n log2 n/ε2 ) space algorithm

Our first algorithm follows an approach that was used in several previous work [14, 29, 28]. The
basic idea is to maintain the min-cut up to some size k using small space. We achieve this by
maintaining a sparse (k + 1)-certificate and incorporating it into the incremental exact min-cut
algorithm due to Henzinger [14], as described in Section 4. Finally we apply the well-known
randomized sparsification result due to Karger [17] to obtain our result.
Maintaining min-cut up to size k using O(kn) space. We incrementally maintain an msfd
for an unweighted graph G using k + 1 union-find data structures F1 , . . . , Fk+1 (see [6]). Each Fi
maintains a spanning forest Fi of G. Recall that F1 , . . . , Fk+1 are edge-disjoint. When a new edge
e = (u, v) is inserted into G, we define i to be the first index such that Fi .Find(u) 6= Fi .Find(v).
If we found such an i, we append the edge e to the forest Fi by setting Fi .Union(u, v) and return
9

i. If such an i cannot be found after k + 1 steps, we simply discard edge e and return NULL. We
refer to such procedure as (k + 1)-Connectivity(e).
It is easy to see that the forests maintained by (k+1)-Connectivity(e) for every newly inserted
edge e are indeed edge-disjoint. Combining this procedure with techniques from Henzinger [14] leads
to the following Algorithm 2.
Algorithm 2 Incremental Exact Min-Cut up to size k
1: Set λ = 0, initialize k union-find data structures F1 , . . . , Fk+1 ,
k empty forests F1 , . . . , Fk+1 , I(G, λ), and an empty cactus tree.
2: while there is at least one minimum cut of size λ do
Receive the next operation.
if it is a query then return λ
else it is the insertion of an edge e, then
Set i = (k + 1)-Connectivity(e).
if i 6= NULL then
Set Fi = Fi ∪ {e}.
Update the cactus tree according to the insertion of the edge e.
endif
endif
endwhile
3: Set λ = λ + 1.
S
Let G′ = (V, E ′ ) be a graph with E ′ = I(G, λ − 1) ∪ i≤λ+1 Fi .
Compute I(G′ , λ) and a cactus tree of G′ .
Goto 2.
The correctness of the above algorithm is immediate from Lemmas 4.2 and 4.4. The running
time and query bounds follow from Theorem 8 of Henzinger [14]. For the sake of completeness, we
provide here a full proof.
Corollary 5.1. For k > 0, there is an O(kn) space algorithm that processes a stream of edge
insertions starting from any empty graph G and maintains an exact value of min{λ(G), k}. Starting
from an empty graph, the total time for inserting m edges is O(kmα(n) log n) and queries can be
answered in constant time, where α(n) stands for the inverse of Ackermann function.
Proof. We first analyse Step 1. Initializing k + 1 union-find data structures takes O(kn) time.
The running time for constructing I(G, λ) and building an empty cactus tree is also dominated by
O(kn). Thus, the total time for Step 1 is O(kn).
Let λ0 , . . . , λf , where λf ≤ k, be the values that λ assumes in Step 2 during the execution of the
algorithm in increasing order. We define Phase i to be all steps executed while λ = λi . For i ≥ 1,
we can view Phase i as the i-th execution of Step 3 followed by the execution of Step 2. Let ui
denote the number of edge insertion in Phase i. The total time for testing the (k + 1)-connectivity
of the endpoints of the newly inserted edges, and updating the cactus tree in Step 2 is dominated
by O(n + kα(n)ui ). Since the graph G′ in Step 3 has always at most O(kn) edges, the running
time to compute I(G′ , λ) and the cactus tree of G′ is O(kn log n). Combining the above bounds,
the total time spent in Phase i is O(k(α(n)ui + n log n)). Thus, the total work over all phases is
O(kmα(n) log n).
The space complexity of the algorithm is only O(kn), since we always maintain at most k + 1
spanning forests during its execution.

10

Dealing with min-cuts of arbitrary size. We observe that Corollary 5.1 gives polylogarithmic
amortized update time only for min-cuts up to some polylogarithmic size. For dealing with mincuts of arbitrary size, we use the well-known sampling technique due to Karger [17]. This allows
us to get an (1 + ε)-approximation to the value of a min-cut with high probability.
Lemma 5.2 ([17]). Let G be any graph with minimum cut λ and let p ≥ 12(log n)/(ε2 λ). Let G(p)
be a subgraph of G obtained by including each of edge of G to G(p) with probability p independently.
Then the probability that the value of any cut of G(p) has value more than (1 + ε) or less than
(1 − ε) times its expected value is O(1/n4 ).
For some integer i ≥ 1, let Gi denote a subgraph of G obtained by including each edge of G to
Gi with probability 1/2i independently. We now have all necessary tools to present our incremental
algorithm.
Algorithm 3 (1 + ε)-Min-Cut with O(n log2 n/ε2 ) Space
1: For i = 0, . . . , ⌊log n⌋, let Gi be an initially empty sampled subgraph.
2: Receive the next operation.
if it is a query then
Find the minimum j such that λ(Gj ) ≤ k and return 2j λ(Gj )/(1 − ε).
else it is the insertion of an edge e, then
Include edge e to each Gi with probability 1/2i .
Maintain the exact min cut of each Gi up to size k = 48 log n/ε2 using Algorithm 2.
endif
3: Goto 2.
Theorem 5.3. There is an O(n log2 n/ε2 ) space randomized algorithm that processes a stream of
edge insertions starting from an empty graph G and maintains a (1 + ε)-approximation to a mincut of G with high probability. The amortized update time per operation is O(α(n) log 3 n/ε2 ) and
queries can be answered in O(log n) time.
Proof. We first prove the correctness of the algorithm. For an integer t ≥ 0, let G(t) = (V, E (t) )
be the graph after the first t edge insertions. Further, let λ(G(t) ) denote the min-cut of G(t) ,
p(t) = 12(log n)/(ε2 λ(t) ) and λ(G, S) = |EG (S, V \ S)|, for some cut (S, V \ S). For any integer
(t)
i ≤ ⌊log2 1/p(t) ⌋, Lemma 5.2 implies that for any cut (S, V \ S), (1 − ε)/2i λ(G(t) , S) ≤ λ(Gi , S) ≤
(t)
(1 + ε)/2i λ(G(t) , S), with probability 1 − O(1/n4 ). Let (S ∗ , V \ S ∗ ) be a min-cut of Gi , i.e.,
(t)
(t)
λ(Gi , S ∗ ) = λ(Gi ). Setting i = ⌊log2 1/p(t) ⌋, we get that:
(t)

E[λ(Gi )] ≤ λ(G(t) )/2i ≤ 2p(t) λ(G(t) ) ≤ 24 log n/ε2 .
The latter along with the implication of Lemma 5.2 give that for any ε ∈ (0, 1), the size of the
(t)
minimum cut in Gi is at most (1 + ε)24 log n/ε2 ≤ 48 log n/ε2 with probability 1 − O(1/n4 ). Thus,
j ≤ ⌊log2 1/p(t) ⌋ with probability 1 − O(1/n4 ). Additionally, we observe that the algorithm returns
(t)
a (1 + O(ε))-approximation to a min-cut of G(t) w.h.p. since by Lemma 5.2, 2i λ(Gi )/(1 − ε) ≤
(1 + ε)/(1 − ε)λ(G(t) ) = (1 + O(ε))λ(G(t) ) w.h.p. Note that for any t, ⌊log2 1/p(t) ⌋ ≤ ⌊log n⌋, and
thus it is sufficient to maintain only O(log n) sampled subgraphs.
Since our algorithm applies to unweighted simple graphs, we know that t ≤ O(n2 ). Now
applying union bound over all t ∈ {1, . . . O(n2 )} gives that the probability that the algorithm does
not maintain a 1 + O(ε)-approximation is at most O(1/n2 ).
11

The total expected time for maintaining a sampled subgraph is O(mα(n) log 2 n/ε2 ) and the
required space is O(n log n/ε2 ) (Corollary 5.1). Maintaining O(log n) such subgraphs gives an
O(α(n) log 3 n/ε2 ) amortized time per edge insertion and an O(n log2 n/ε2 ) space requirement. The
O(log n) query time follows as in the worst case we scan at most O(log n) subgraphs, each answering
a min-cut query in constant time.

5.2

Improving the space to O(n log n/ε2 )

We next show how to bring down the space requirement of the previous algorithm to O(n log n/ε2 )
without degrading its running time. The main idea is to keep a single sampled subgraph instead
of O(log n) of them.
Let G = (V, E) be an unweighted undirected graph and assume each edge is given some random
weight pe chosen uniformly from [0, 1]. Let Gw be the resulting weighted graph. For any p > 0, we
denote by G(p) the unweighted subgraph of G that consists of all edges that have weight at most
p. We state the following lemma due to Karger [15]:
Lemma 5.4. Let k = 48 log n/ε2 . Given a connected graph G, let p be a value such that p ≥
k/(4λ(G)). Then with high probability, λ(G(p)) ≤ k and λ(G(p))/p is an (1 + ε)-approximation to
a min-cut of G.
Proof. Since the weight of every edge is uniformly distributed, the probability that an edge has
weight at most p is exactly p. Thus, G(p) is a graph that contains every edge of G with probability
p. The claim follows from Lemma 5.2.
For any graph G and some appropriate weight p ≥ k/(4λ(G)), the above lemma tells us that the
min-cut of G(p) is bounded by k with high probability. Thus, instead of considering the graph G
along with its random edge weights, we build a collection of k + 1 minimum edge-disjoint spanning
forests (using those edge weights). We note that such a collection is an msfd of order k + 1 for G
with O(kn) edges and by Lemma 4.2, it preserves all minimum cuts of G up to size k.
Our algorithm uses the following two data structures:
(1) NI-Sparsifier(k) data-structure: Given a graph G, where each edge e is assigned some
weight pe and some parameter k, we devise an insertion-only data-structure that maintains a
collection of k + 1Sminimum edge-disjoint spanning forests F1 , . . . , Fk+1 with respect to the edge
weights. Let F = i≤k+1 Fi . Since we are in the incremental setting, it is known that the problem
of maintaining a single minimum spanning forest can be solved in time O(log n) per insertion using
the dynamic tree structure of Sleator and Tarjan [27]. Specifically, we use this data-structure
to determine for each pair of nodes (u, v) the maximum weight of an edge in the cycle that the
edge (u, v) induces in the minimum spanning forest Fi . Let max-weight(Fi (u, v)) denote such a
maximum weight. The update operation works as follows: when a new edge e = (u, v) is inserted
into G, we first use the dynamic tree data structure to test whether u and v belong to the same
tree. If no, we link their two trees with the edge (u, v) and return the pair (TRUE, NULL) to
indicate that e was added to Fi and no edge was evicted from Fi . Otherwise, we check whether
pe > max-weight(Fi (e)). If the latter holds, we make no changes in the forest and return (FALSE,
e). Otherwise, we replace one of the maximum edges, say e′ , on the path between u and v in the
tree by e and return (TRUE, e′ ). The boolean value that is returned indicates whether e belongs
to Fi or not, the second value that is returned gives an edge that does not (or no longer) belong
to Fi . Note that each edge insertion requires O(log n) time. We refer to this insert operation as
Insert-MSF(Fi , e, pe ).
Now, the algorithm that maintains the weighted minimum spanning forests implements the
following operations:
12

• Initialize-NI(k): Initializes the data structure for k + 1 empty minimum spanning forests.
• Insert-NI(e, pe ): Set i = 1, e′ = e, taken = FALSE.
while ((i ≤ k + 1) and e′ 6= NULL) do
Set (t′ , e′′ ) = Insert-MSF(Fi , e′ , pe′ ).
if (e′ = e) then set taken = t′ endif
Set e′ = e′′ and i = i + 1.
endwhile
if (e′ 6= e) then return (taken, e′ ) else return (taken, NULL).
The boolean value that is returned indicates whether e belongs to F or not, the second value
returns an edge that S
is removed from F , if any.
Recall that F = i≤k+1 Fi . We use the abbreviation NI-Sparsifier(k) to refer to this datastructure. Throughout the algorithm we will associate a weight with each edge in F and use F w
to refer to this weighted version of F .
Lemma 5.5. For k > 0 and any graph G, NI-Sparsifier(k) maintains a weighted mfsd of order
k + 1 of G under edge insertions. The algorithm uses O(kn) space and the total time for inserting
m edges is O(km log n).
Proof. We first show that NI-Sparsifier(k) maintains a forest decomposition such that (1) the
forests are edge-disjoint and (2) each forest is maximal. We proceed by induction on the number
m of edge insertions.
For m = 0, the forest decomposition is empty. Thus the edge-disjointness and maximality of
forests trivially hold. For m > 0, consider the m-th edge insertion, which inserts an edge e. Let F ′ ,
resp. F , denote the union of forests before, resp. after, the insertion of edge e. By the inductive
assumption, F ′ satisfies (1) and (2). If F = F ′ , i.e., the edge e was not added to any of the forests
when Insert-NI(e, pe ) was called, then F also satisfies (1) and (2). Otherwise F 6= F ′ and note
that by construction, e is appended to exactly one forest. Let Fj′ , resp. Fj , denote such maximal
forest before, resp. after, the insertion of e. We distinguish two cases. If e links two trees of Fj′ ,
then Fj is also a maximal forest and forests of F are edge-disjoint. Thus F satisfies (1) and (2).
Otherwise, the addition of e results in the deletion of another edge e′ ∈ Fj′ . It follows that Fj is
maximal and the current forests are edge-disjoint. Applying a similar argument to the addition of
edge e′ in the remaining forests, we conclude that F satisfies (1) and (2).
We next argue about time and space complexity. The dynamic tree data structure can be
implemented in O(n) space, where each query regarding max-weight(Fi (u, v)) can be answered in
O(log n) time. Since the algorithm maintains k + 1 such forests, the space requirement is O(kn).
The total running time follows since insertion of an edge can result in at most k + 1 executions of
the Insert-MSF(Fi, e, pe ) procedures, each running in O(log n) time.
(2) Limited Exact Min-Cut(k) data-structure: We use Algorithm 2 to implement the following operations for any unweighted graph G and parameter k,
• Insert-Limited(e): Executes the insertion of edge e using Algorithm 2.
• Query-Limited(): Returns λ.
• Initialize-Limited(G, k): Builds a data structure for G with parameter k by executing Step
1 of Algorithm 2 and then Insert-Limited(e) for each edge e in G.
We use the abbreviation Lim(k) to refer to such data-structure.
Combining the above data-structures leads to Algorithm 4.
13

Algorithm 4 (1 + ε)-Min-Cut with O(n log n/ε2 ) Space
1: Set k = 48 log n/ε2 .
Set p = 12 log n/ε2 .
Let H and F w be empty graphs.
2: Initialize-Limited(H, k).
while Query-Limited() < k do
Receive the next operation.
if it is a query then return Query-Limited()/ min{1, p}.
else it is the insertion of an edge e, then
Sample a random weight from [0, 1] for the edge e and denote it by pe .
if pe ≤ p then Insert-Limited(e) endif
Set (taken, e′ ) = Insert-NI(e, pe ).
if taken then
Insert e into F w with weight pe .
if (e′ 6= NULL) then remove e′ from F w .
endif
endif
endwhile
3: // Rebuild Step
Set p = p/2.
Let H be the unweighted subgraph of F w consisting of all edges of weight at most p.
Goto 2.
Correctness and Running Time Analysis. Throughout the execution of Algorithm 4, F
corresponds exactly to the msfd of order k + 1 of G maintained by NI-Sparsifier(k). In the
following, let H be the graph that is given as input to Lim(k). Thus, by Corollary 5.1, QueryLimited() returns min{k, λ(H)}, i.e., it returns λ(H) as long as λ(H) ≤ k. We now formally prove
the correctness.
Lemma 5.6. Let ǫ ≤ 1, k = 48 log n/ε2 and assume that the algorithm is started on an empty
graph. As long as λ(G) < k, we have H = G, p = k/4, and Query-Limited() returns λ(G). The
first rebuild step is triggered after the first insertion that increases λ(G) to k and at that time, it
holds that λ(G) = λ(H) = k.
Proof. The algorithm starts with an empty graph G, i.e., initially λ(G) = 0. Throughout the
sequence of edge insertions λ(G) never decreases. We show by induction on the number m of edge
insertions that H = G and p = k/4 as long as λ(G) < k.
Note that k/4 ≥ 1 by our choice of ǫ. For m = 0, the graphs G and H are both empty graphs
and p is set to k/4. For m > 0, consider the m-th edge insertion, which inserts an edge e. Let
G and H denote the corresponding graphs after the insertion of e. By the inductive assumption,
p = k/4 and G \ {e} = H \ {e}. As p ≥ 1, e is added to H and, thus, it follows that G = H. Hence,
λ(H) = λ(G). If λ(G) < k but λ(G \ {e}) < k, no rebuild is performed and p is not changed. If
λ(G) = k, then the last insertion was exactly the insertion that increased λ(G) from k − 1 to k.
As H = G before the rebuild, Query-Limited() returns k, triggering the first execution of the
rebuild step.
We next analyze the case that λ(G) ≥ k. In this case, both H and p are random variables, as
they depend on the randomly chosen weights for the edges. Let F (p) be the unweighted subgraph
14

of F w that contains all edges of weight at most p.
Lemma 5.7. Let Nh (p) be the graph consisting of all edges that were inserted after the last rebuild
and have weight at most p and let F old (p) be F (p) right after the last rebuild. Then it holds that
H = F old (p) ∪ Nh (p).
Proof. Up to the first rebuild, Nh = G and p ≥ 1. Thus Nh (p) = Nh = G. Lemma 5.6 shows that
until the first rebuild H = G. As F old (p) = ∅, it follows that H = G = Nh (p) ∪ F old (p) up to the
first rebuild.
Immediately after each rebuild step, Nh = ∅ and H is set to be F (p), thus the claim holds.
After each subsequent edge insertion that does not trigger a rebuild, the newly inserted edge is
added to Nh (p) and to H iff its weight is at most p. Thus, both Nh (p) and H change in the same
way, which implies that H = F old (p) ∪ Nh (p).
Lemma 5.8. At the time of a rebuild F (p) is an msfd of order k + 1 of G(p).
Proof. NI-sparsifier maintains a maximal spanning forest decomposition based on minimumweight spanning forests F1 , . . . Fk+1 of G using the weights pe . Now consider the hierarchical
decomposition F1 (p), . . . , Fk+1 (p) of G(p) induced by taking only the edges of weight at most p of
each forest Fi . Note that NI-sparsifier would return exactly the same hierarchy F1 (p), . . . , Fk+1 (p)
if only the edges of G(p) were inserted into NI-sparsifier. Thus F1 (p), . . . , Fk+1 (p) is an msfd of
order k + 1 of G(p).
In order to show that λ(H)/ min{1, p} is an (1+ε)-approximation of λ(G) with high probability,
we need to show that if λ(G) ≥ k then (a) the random variable p is at least k/(4λ(G)) w.h.p., which
implies that λ(G(p)) is a (1 + ε)-approximation of λ(G) w.h.p. and (b) that λ(H) = λ(G(p)) (by
Lemma 5.4).
Lemma 5.9. Let ε ≤ 1. If λ(G) ≥ k, then (1) p ≥ k/(4λ(G)) with probability 1 − O(log n/n4 ) and
(2) λ(H) = λ(G(p)).
Proof. For any i ≥ 0, after the i-th rebuild we have p = p(i) := 12 log n/(2i ε2 ). Let ℓ =
⌊log(12 log n/ε2 )⌋ denote the index of the last rebuild at which p(i) ≥ 1. For any i ≥ ℓ + 1,
we will show by induction on i that (1) p(i) = 12 log n/(2i ε2 ) ≥ 12 log n/(ε2 λ(G)) with probability
1 − O((i − 1 − ℓ)/n4 ), which is equivalent to showing that λ(G) ≥ 2i and that (2) at any point
between the i − 1-st and the i-th rebuild, λ(H) = λ(G(p(i−1) )).
Once we have shown this, we can argue that the number of rebuild steps is small, thus giving the
claimed probability in the lemma. Indeed, note that λ(G) ≤ n since G is unweighted. Additionally,
from above we get that after the i-th rebuild, λ(G) ≥ 2i with high probability. Combining these
two bounds yields i ≤ O(log n) w.h.p., i.e., the number of rebuild steps is at most O(log n).
We first analyse i = ℓ + 1. Note that ℓ + 1 is the index of the first rebuild at which p(i) < 1.
Assume that the insertion of some edge e caused the first rebuild. Lemma 5.6 showed that (1) at
the first rebuild λ(G) = k and (2) that up to the first rebuild G(p) = G = H. We observe that (1)
and (2) remain true up to the (ℓ + 1)-st rebuild. In addition, λ(G) = k ≥ 24 log n/ε2 ≥ 2i , which
implies that p(i) ≥ 1/2. This shows the base case.
For the induction step (i > ℓ + 1), we inductively assume that (1) at the (i − 1)-st rebuild,
p(i−1) ≥ 12 log n/(ε2 λ(Gold )) with probability 1 − O((i − 2 − ℓ)/n4 ), where Gold is the graph
G right before the insertion that triggered the i-th rebuild (i.e., at the last point in time when
Query-Limited() returned a value less than k), and (2) that λ(H) = λ(G(p(i−2) )) at any time
between the (i − 2)-nd and the (i − 1)-st rebuild. Let e be the edge whose insertion caused the i-th
15

rebuild. Define Gnew = Gold ∪ {e}. By induction hypothesis, with probability 1 − O((i − 2 − ℓ)/n4 ),
p(i−1) ≥ 12 log n/(ε2 λ(Gold )) ≥ 12 log n/(ε2 λ(Gnew )) as λ(Gold ) ≤ λ(Gnew ). Thus, by Lemma
5.4, we get that λ(Gnew (p(i−1) ))/p(i−1) ≤ (1 + ε)λ(Gnew ) with probability 1 − O(1/n4 ). Applying
an union bound, we get that the two previous statements hold simultaneously with probability
1 − O((i − 1 − ℓ)/n4 ).
We show below that λ(Gnew (p(i−1) )) = λ(H new ), where H new is the graph stored in Lim(k)
right before the i-th rebuild. Thus, λ(H new ) = k, which implies that
λ(Gnew (p(i−1) )) = k = 48 log n/ε2 ≤ (1 + ε)λ(Gnew ) · p(i−1)

= (1 + ε)λ(Gnew ) · 12 log n/(2i−1 ε2 ),

with probability 1−O((i−1−ℓ)/n4 ). This in turn implies that with probability 1−O((i−1−ℓ)/n4 ),
λ(Gnew ) ≥ 2i+1 /(1 + ε) ≥ 2i by our choice of ε.
It remains to show that λ(Gnew (p(i−1) )) = λ(H new ). Note that this is a special case of (2),
which claims that at any point between that (i − 1)-st and the i-th rebuild λ(H) = λ(G(p(i−1) )),
where H and G are the current graphs. Thus, to complete the proof of the lemma it suffices to
show (2).
As H is a subgraph of G(p(i−1) ), we know that λ(G(p(i−1) )) ≥ λ(H). Thus, we only need to
show that λ(G(p(i−1) )) ≤ λ(H). Let Gi−1 , resp. F i−1 , resp. H i−1 , be the graph G, resp. F , resp. H,
right after rebuild i − 1 and let Nh be the set of edges inserted since, i.e., G = G(i−1) ∪ Nh . As we
showed in Lemma 5.7, H = F i−1 (p(i−1) ) ∪ Nh (p(i−1) ). Thus, H i−1 = F i−1 (p(i−1) ). Additionally, by
Lemma 5.8, F i−1 (p(i−1) ) is an msfd of order k + 1 of Gi−1 (p(i−1) ). Thus by Lemma 3.2, for every
cut (A, V \ A) of value at most k in H i−1 , λ(H i−1 , A) = λ(F i−1 (p(i−1) ), A) = λ(Gi−1 (p(i−1) ), A),
where λ(G, A) = |EG (A, V \ A)|. Now assume towards contradiction that λ(G(p(i−1) )) > λ(H)
and consider a minimum cut (A, V \ A) in H, i.e., λ(H) = λ(H, A). We know that at any time
k ≥ λ(H). Thus k ≥ λ(H) = λ(H, A), which implies k ≥ λ(H i−1 , A). By Lemma 3.2 it follows that
λ(H i−1 , A) = λ(Gi−1 (p(i−1) ), A). Note that H = H i−1 ∪ Nh (p(i−1) ) and G(p(i−1) ) = Gi−1 (p(i−1) ) ∪
Nh (p(i−1) ). Let x be the number of edges of Nh (p(i−1) ) that cross the cut (A, V \ A). Then
λ(H) = λ(H, A) = λ(H i−1 , A) + x = λ(Gi−1 (p(i−1) ), A) + x = λ(G(p(i−1) ), A), which contradicts
the assumption that λ(G(p(i−1) )) > λ(H).
Since our algorithm is incremental and applies only to unweighted graphs, we know that there
can be at most O(n2 ) edge insertions. The above lemma implies that for any current graph G,
Algorithm 4 returns a (1 + ε)-approximation to a min-cut of G with probability 1 − O(log n/n4 ).
Applying an union bound over O(n2 ) possible different graphs, gives that the probability that the
algorithm does not maintain a (1 + ε)-approximation is at most O(log n/n2 ) = O(1/n). Thus, at
any time we return a (1 + ε)-approximation with probability 1 − O(1/n).
Theorem 5.10. There is an O(n log n/ε2 ) space randomized algorithm that processes a stream of
edge insertions starting from an empty graph G and maintains a (1+ε)-approximation to a min-cut
of G with high probability. The total time for insertiong m edges is O(mα(n) log3 n/ε2 ) and queries
can be answered in constant time.
Proof. The space requirement is O(n log n/ε2 ) since at any point of time, the algorithm keeps H,
F w , Lim(k), and NI-Sparsifier (k), each of size at most O(n log n/ε2 ) (Corollary 5.1 and Lemma
5.5).
When Algorithm 4 executes a Rebuild Step, only the Lim(k) data-structure is rebuilt, but not
NI-Sparsifier(k). During the whole algorithm m Insert-NI operations are performed. Thus, by
Lemma 5.5, the total time for all operations involving NI-Sparsifier(k) is O(m log2 n/ε2 ).
16

It remains to analyze Steps 2 and 3. In Step 2, Initialize-Limited(H, k) takes at most
O(mα(n) log2 n/ε2 ) total time (Corollary 5.1). The running time of Step 3 is O(m) as well. Since
the number of Rebuild Steps is at most O(log n), it follows that the total time for all InitializeLimited(H, k) calls in Steps 2 and the total time of Step 3 throughout the execution of the algorithm
is O(mα(n) log 3 n/ε2 ).
We are left with analyzing the remaining part of Step 2. Each query operation executes one
Query-Limited() operation, which takes constant time. Each insertion executes one InsertNI(e, pe ) operation, which takes amortized time O(log2 n/ε). We maintain the edges of F w in a
balanced binary tree so that each insertion and deletion takes O(log n) time. As there are m edge
insertions the remaining part of Step 2 takes total time O(m log2 n/ε2 ). Combining the above
bounds gives the theorem.
Acknowledgements The research leading to these results has received funding from the European Research Council under the European Union’s 7th Framework Programme (FP/2007-2013) /
ERC Grant Agreement no. 340506 for M. Henzinger. M. Thorup’s research is partly supported by
Advanced Grant DFF-0602-02499B from the Danish Council for Independent Research under the
Sapere Aude research career programme. This work was done in part while M. Henzinger and M.
Thorup were visiting the Simons Institute for the Theory of Computing.

References
[1] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower
bounds for dynamic problems. In Proc. of the 55th FOCS, pages 434–443. IEEE, 2014.
[2] Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Proc.
of the 36th ICALP, pages 328–338, 2009.
[3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proc. of the 32nd PODS, pages 5–14, 2012.
[4] András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and
flows in capacitated graphs. SIAM J. Comput., 44(2):290–319, 2015.
[5] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E.
Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass
dynamic streams. In Proc. of the 47th STOC, pages 173–182, 2015.
[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction
to Algorithms (3. ed.). MIT Press, 2009.
[7] E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. On the structure of a family of minimum
weighted cuts in a graph. Studies in Discrete Optimization, pages 290–306, 1976.
[8] Yefim Dinitz and Jeffery Westbrook. Maintaining the classes of 4-edge-connectivity in a graph
on-line. Algorithmica, 20(3):242–276, 1998.
[9] Harold N. Gabow. Applications of a poset representation to edge connectivity and graph
rigidity. In Proc. of the 32nd FOCS, pages 812–821, 1991.
[10] Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences.
J. Comput. Syst. Sci., 50(2):259–273, 1995.
17

[11] 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.
[12] 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.
[13] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of the 47th STOC, pages 21–30, 2015.
[14] Monika Rauch Henzinger. A static 2-approximation algorithm for vertex connectivity and
incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms,
24(1):194–220, 1997.
[15] David Karger. Random Sampling in Graph Optimization Problems. PhD thesis, Stanford
University, Stanford, 1994.
[16] David R. Karger. Using randomized sparsification to approximate minimum cuts. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January
1994, Arlington, Virginia., pages 424–432, 1994.
[17] David R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper.
Res., 24(2):383–413, 1999.
[18] David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46–76, 2000.
[19] Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic global minimum cut of a simple
graph in near-linear time. In Proc. of the 47th STOC, pages 665–674, 2015.
[20] Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting.
Theory Comput. Syst., 53(2):243–262, 2013.
[21] Jakub Lacki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in
O(n log log n) time. In Proc. of the 19th ESA, pages 155–166, 2011.
[22] Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 1(10):96–115, 1927.
[23] Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse kconnected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583–596, 1992.
[24] Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York, NY, USA, 1 edition, 2008.
[25] Danupon Nanongkai and Thatchaphol Saranurak. Dynamic cut oracle. under submission,
2016.
[26] Johannes A. La Poutré. Maintenance of 2- and 3-edge-connected components of graphs II.
SIAM J. Comput., 29(5):1521–1549, 2000.
[27] Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J.
Comput. Syst. Sci., 26(3):362–391, 1983.
[28] Mikkel Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91–127, 2007.
[29] Mikkel Thorup and David R Karger. Dynamic graph algorithms with applications. In Algorithm Theory-SWAT 2000, pages 1–9. Springer, 2000.
18

A

Missing proofs in Section 3

Next we show a proof for Lemma 3.2. The arguments closely follow the work of Nagamochi and
Ibaraki [24]. We first present the following helpful lemma.
Lemma A.1. Let F = (F1 , . . . , Fm ) be an msfd ofSorder m of a graph G = (V, E). Then for any
edge (u, v) ∈ Fj and any i ≤ j, it holds that λ(u, v, l≤i Fl ) ≥ i.

Proof. Fix some edge e = (u, v) ∈ Fj . We first argue that for each i = 1, . . . , j − 1, the forest (V, Fi )
contains some (u, v)-path. Indeed, by the maximality of the forest (V, Fi ), the graph (V, Fi ∪ {e})
must have some cycle
S C that contains e. Thus, P = C \ e is the (u, v)-path in theSforest (V, Fi ).
It follows that (V, l≤i Fl ) has i edge-disjoint paths. Next, observe that Gj = (V, l≤j Fl ) has j
edge-disjoint paths, namely the j − 1 edge disjoint paths in Gj−1 (whichSdoes not contain the edge
(u, v)) and the 1-edge path consisting of the edge (u, v). Hence, λ(u, v, l≤i Fl ) ≥ i,
Proof of Lemma 3.2: Assume that λ(S, G) ≤ k − 1. Then by definition of Gk , we know that
Gk preserves any cut S of size up to k. Thus λ(S, Gk ) = λ(S, G).
For the other case, λ(S, G) ≥ k and assume that λ(S, Gk ) < λ(S, G) (otherwiseSthe lemma
follows). Then there is an edge e = (u, v) ∈ EG (S, V \ S) \ EGk (S, V \ S). Since e 6∈ i≤k Fi , this
means that e belongs to some forest Fj with j > k. By Lemma A.1, we have that λ(u, v, Gk ) ≥ k.
Since (S, V \ S) separates u and v in Gk , it follows that λ(S, Gk ) = |EGk (S, V \ S)| ≥ λ(u, v, Gk ) ≥
k.

19

