On Fully Dynamic Graph Sparsifiers
Ittai Abraham∗

David Durfee†

Ioannis Koutis‡

Sebastian Krinninger§

arXiv:1604.02094v2 [cs.DS] 7 Oct 2016

Richard Peng¶

Abstract
We initiate the study of fast dynamic algorithms for graph sparsification problems and
obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take
polylogarithmic time after each update in the graph. Our three main results are as follows. First,
we give a fully dynamic algorithm for maintaining a (1 ± )-spectral sparsifier with amortized
update time poly(log n, −1 ). Second, we give a fully dynamic algorithm for maintaining a
(1 ± )-cut sparsifier with worst-case update time poly(log n, −1 ). Both sparsifiers have size
n · poly(log n, −1 ). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic
algorithm for maintaining a (1 + )-approximation to the value of the maximum flow in an
unweighted, undirected, bipartite graph with amortized update time poly(log n, −1 ).

∗

VMware Research
Georgia Institute of Technology
‡
University of Puerto Rico, Rio Piedras
§
Max Planck Institute for Informatics, Saarland Informatics Campus, Germany
¶
Georgia Institute of Technology
†

i

Contents
1

1 Introduction
2 Background
2.1 Dynamic Graph Algorithms . . . . . . . . . . .
2.2 Running Times and Success Probabilities . . .
2.3 Cuts and Laplacians . . . . . . . . . . . . . . .
2.4 Graph Approximations . . . . . . . . . . . . . .
2.5 Sampling Schemes for Constructing Sparsifiers
2.6 Spanning Trees and Spanners . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2
2
3
3
4
4
5

3 Overview and Related Work
3.1 Dynamic Spectral Sparsifier . . . . . . . . . . .
3.2 Dynamic Cut Sparsifier . . . . . . . . . . . . .
3.3 (1 − )-Approximate Undirected Bipartite Flow
3.4 Discussion . . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

5
. 5
. 7
. 8
. 10

4 Dynamic Spectral Sparsifier
4.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . .
4.2 Spectral Sparsification . . . . . . . . . . . . . . . . . . . . .
4.3 Decremental Spanner with Monotonicity Property . . . . .
4.4 Decremental Spectral Sparsifier . . . . . . . . . . . . . . . .
4.5 Turning Decremental Spectral Sparsifier into Fully Dynamic

. . . . .
. . . . .
. . . . .
. . . . .
Spectral

. . . . . .
. . . . . .
. . . . . .
. . . . . .
Sparsifier

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

11
12
13
16
20
22

5 Dynamic Cut Sparsifier
5.1 Algorithm Overview . . . . . . . . . . . . . . . .
5.2 Definitions . . . . . . . . . . . . . . . . . . . . . .
5.3 A Simple Cut Sparsification Algorithm . . . . . .
5.4 Dynamic Cut Sparsifier . . . . . . . . . . . . . .
5.5 Handling Arbitrarily Long Sequences of Updates

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

23
24
25
25
27
30

6 Application of Dynamic Cut Sparsifier: Undirected Bipartite Min-Cut
6.1 Key Observations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Dynamic Algorithm for Maintaining a Minimum s − t Cut on Bipartite Graphs . . .
6.3 Dynamically Updating Data Structures . . . . . . . . . . . . . . . . . . . . . . . . .

32
32
34
36

7 Vertex Sampling in Bipartite Graphs

39

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

8 Maintaining (1 + )-Approximate Undirected Bipartite Min-Cut
45
8.1 Vertex Sparsification in Quasi-Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . 45
8.2 Dynamic Minimum Cut of Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . 51
A Omitted Proofs of Section 4.2

62

B Guarantees of Combinatorial Reductions

64

ii

1

Introduction

Problems motivated by graph cuts are well studied in theory and practice. The prevalence of
large graphs motivated sublinear time algorithms for cut based problems such as clustering [ST13,
BBC+ 12, ACL06, AP09, OV11, GT12]. In many cases such as social networks or road networks,
these algorithms need to run on dynamically evolving graphs. In this paper, we study an approach
for obtaining sublinear time algorithms for these problems based on dynamically maintaining graph
sparsifiers.
Recent years have seen a surge of interest in dynamic graph algorithms. On the one hand, very
efficient algorithms, with polylogarithmic running time per update in the graph, could be found
for some key problems in the field [HK99, HLT01, KKM13, OR10, NS13, BGS15, BHI15, BKS12,
ACD+ 16]. On the other hand, there are polynomial conditional lower bounds for many basic graph
problems [Pat10, AVW14, HKN+ 15]. This leads to the question which problems can be solved
with polylogarithmic update time. Another relatively recent trend in graph algorithmics is graph
sparsification where we reduce the size of graphs while approximately preserving key properties
such as the sizes of cuts [BK15]. These routines and their extensions to the spectral setting [ST11,
BSS+ 13] play central roles in a number of recent algorithmic advances [Mad10, She13, KLO+ 14,
PS14, ST14, KLP+ 16, Pen16], often leading to graph algorithms that run in almost-linear time. In
this paper, we study problems at the intersection of dynamic algorithms and graph sparsification,
leveraging ideas from both fields.
At the core of our approach are data structures that dynamically maintain graph sparsifiers in
polylog n time per edge insertion or deletion. They are motivated by the spanner based constructions
of spectral sparsifiers of Koutis [Kou14]. By modifying dynamic algorithms for spanners [BKS12],
we obtain data structures that spend amortized polylog n per update. Our main result for spectral
sparsifiers is:
Theorem 1.1. Given a graph with polynomially bounded edge weights, we can dynamically maintain
a (1 ± )-spectral sparsifier of size n · poly(log n, −1 ) with amortized update time poly(log n, −1 )
per edge insertion / deletion.
When used as a black box, this routine allows us to run cut algorithms on sparse graphs instead
of the original, denser network. Its guarantees interact well with most routines that compute
minimum cuts or solve linear systems in the graph Laplacian. Some of them include:
1. min-cuts, sparsest cuts, and separators [She09],
2. eigenvector and heat kernel computations [OSV12],
3. approximate Lipschitz learning on graphs [KRS+ 15] and a variety of matrix polynomials in
the graph Laplacian [CCL+ 15].
In many applications the full power of spectral sparsifiers is not needed, and it suffices to work
with a cut sparsifier. As spectral approximations imply cut approximations, research in recent years
has focused spectral sparsification algorithms [KL13, KLP12, KLM+ 14, ZLO15, LS15, JK15]. In the
dynamic setting however we get a strictly stronger result for cut sparsifiers than for spectral sparsifiers:
we can dynamically maintain cut sparsifiers with polylogarithmic worst-case update time after each
insertion / deletion. We achieve this by generalizing Koutis’ sparsification paradigm [Kou14] and
replacing spanners with approximate maximum spanning trees in the construction. While there are
no non-trivial results for maintaining spanners with worst-case update time, spanning trees can be
1

maintained with polylogarithmic worst-case update time by a recent breakthrough result [KKM13].
This allows us to obtain the following result for cut sparsifiers:
Theorem 1.2. Given a graph with polynomially bounded edge weights, we can dynamically maintain
a (1 ± )-cut sparsifier of size n · poly(log n, −1 ) with worst-case update time poly(log n, −1 ) per
edge insertion / deletion.
We then explore more sophisticated applications of dynamic graph sparsifiers. A key property of
these sparsifiers is that they have arboricity polylog n. This means the sparsifier is locally sparse, and
can be represented as a union of spanning trees. This property is becoming increasingly important
in recent works [NS13, PS16]: Peleg and Solomon [PS16] gave data structures for maintaining
approximate maximum matchings on fully dynamic graphs with amortized cost parameterized by
the arboricity of the graphs. We demonstrate the applicability of our data structures for designing
better data structures on the undirected variant of the problem. Through a two-stage application of
graph sparsifiers, we obtain the first non-separator based approach for dynamically maintaining
(1 − )-approximate maximum flow on fully dynamic graphs:
Theorem 1.3. Given a dynamically changing unweighted, undirected, bipartite graph G = (A, B, E)
with demand −1 on every vertex in A and demand 1 on every vertex in B, we can maintain a
(1 − )-approximation to the value of the maximum flow, as well as query access to the associated
approximate minimum cut, with amortized update time poly(log n, −1 ) per edge insertion / deletion.
To obtain this result we give stronger guarantees for vertex sparsification in bipartite graphs, identical to the terminal cut sparsifier question addressed by Andoni, Gupta, and Krauthgamer [AGK14].
Our new analysis profits from the ideas we develop by going back and forth between combinatorial
reductions and spectral sparsification. This allows us to analyze a vertex sampling process via a
mirror edge sampling process, which is in turn much better understood.
Overall, our algorithms bring together a wide range of tools from data structures, spanners, and
randomized algorithms. We will provide more details on our routines, as well as how they relate to
existing combinatorial and probabilistic tools in Section 3.

2
2.1

Background
Dynamic Graph Algorithms

In this paper we consider undirected graphs G = (V, E) with n vertices and m edges that are either
unweighted or have non-negative edge weights. We denote the weight of an edge e = (u, v) in a
graph G by wG (e) or wG (u, v) and the ratio between the largest and the smallest edge weight by
W . The weight wG (F ) of a set of edges F ⊆ E is the sum of the individual edge weights. We will
assume that all weights are polynomially bounded because there are standard reductions from the
general case using minimum spanning trees (e.g. [SS11] Section 10.2., [EES+ 08] Theorem 5.2).
Also, these contraction schemes in the data structure setting introduces another layer of complexity
akin to dynamic connectivity, which we believe is best studied separately.
A dynamic algorithm is a data structure for dynamically maintaining the result of a computation
while the underlying input graph is updated periodically. We consider two types of updates:
edge insertions and edge deletions. An incremental algorithm can handle only edge insertions, a
decremental algorithm can handle only edge deletions, and a fully dynamic algorithm can handle
both edge insertions and deletions. After every update in the graph, the dynamic algorithm is
2

allowed to process the update to compute the new result. For the problem of maintaining a sparsifier,
we want the algorithm to output the changes to the sparsifier (i.e., the edges to add to or remove
from the sparsifier) after every update in the graph.

2.2

Running Times and Success Probabilities

The running time spent by the algorithm after every update is called update time. We distinguish
between amortized and worst-case update time. A dynamic algorithm has amortized update time
T (m, n, W ), if the total time spent after q updates in the graph is at most qT (m, n, W ). A dynamic
algorithm has worst-case update time T (m, n, W ), if the total time spent after each update in the
graph is at most T (m, n, W ). Here m refers to the maximum number of edges ever contained in the
graph. All our algorithms are randomized.
The guarantees we report in this paper (quality and size of sparsifier, and update time) will
hold with high probability (w.h.p.), i.e. with probability at least 1 − 1/nc for some arbitrarily chosen
constant c ≥ 1. These bounds are against an oblivious adversary who chooses its sequence of
updates independently from the random choices made by the algorithm. Formally, the oblivious
adversary chooses its sequence of updates before the algorithm starts. In particular, this means
that the adversary is not allowed to see the current edges of the sparsifier. As our composition of
routines involve poly(n) calls, we will assume the composability of these w.h.p. bounds.
Most of our update costs have the form O(logO(1) n−O(1) ), where  is the approximation error.
We will often state these as poly(log n, −1 ) when the exponents exceed 3, and explicitly otherwise.

2.3

Cuts and Laplacians

A cut U ⊆ V of G is a subset of vertices whose removal makes G disconnected. We denote by ∂G (U )
the edges crossing the cut U , i.e., the set of edges with one endpoint in U and one endpoint in
V \ U . The weight of the cut U is wG (∂G (U )). An edge cut F ⊆ E of G is a a subset of edges whose
removal makes G disconnected and the weight of the edge cut F is wG (F ). For every pair of vertices
u and v, the local edge connectivity λG (u, v) is the weight of the minimum edge cut separating u
and v. If G is unweighted, then λG (u, v) amounts to the number of edges that have to be removed
from G to make u and v disconnected.
Assuming some arbitrary order v1 , . . . vn on the vertices, the Laplacian matrix LG of an undirected
graph G is the n × n matrix that in row i and column j contains the negated weight −wG (vi , vj )
P
of the edge (vi , vj ) and in the i-th diagonal entry contains the weighted degree nj=1 wG (vi , vj ) of
vertex vi . Note that Laplacian matrices are symmetric. The matrix Le of an edge e of G is the
n × n Laplacian matrix of the subgraph of G containing only the edge e. It is 0 everywhere except
for a 2 × 2 submatrix.
For studying the spectral properties of G we treat the graph as a resistor network. For every
edge e ∈ E we define the resistance of e as rG (e) = 1/wG (e). The effective resistance RG (e) of
an edge e = (v, u) is defined as the potential difference that has to be applied to u and v to drive
one unit of current through the network. A closed form expression of the effective resistance is
†
†
RG (e) = b>
u,v LG bu,v , where LG is the Moore-Penrose pseudo-inverse of the Laplacian matrix of G
and bu,v is the n-dimensional vector that is 1 at position u, −1 at position v, and 0 otherwise.

3

2.4

Graph Approximations

The goal of graph sparsification is to find sparse subgraphs, or similar small objects, that approximately preserve certain metrics of the graph. We first define spectral sparsifiers where we require
that Laplacian quadratic form of the graph is preserved approximately. Spectral sparsifiers play a
pivotal role in fast algorithms for solving Laplacian systems, a special case of linear systems.
Definition 2.1. A (1 ± )-spectral sparsifier H of a graph G is a subgraph of G with weights wH
such that for every vector x ∈ Rn
(1 − )x> LH x ≤ x> LG x ≤ (1 + )x> LH x .
Using the Loewner ordering on matrices this condition can also be written as (1 − )LH  LG 
(1 + )LH . An n × n matrix A is positive semi-definite, written as A  0, if x> Ax ≥ 0 for all x ∈ Rn .
For two n × n matrices A and B we write A  B as an abbreviation for A − B  0.
P
Note that x> LG x = (u,v)∈E w(u, v)(x(u) − x(v))2 where the vector x is treated as a function
on the vertices and x(v) is the value of x for vertex v. A special case of such a function on the
vertices is given by the binary indicator vector xU associated with a cut U , where xU (v) = 1 is
v ∈ U and 0 otherwise. If limited to such indicator vectors, the sparsifier approximately preserves
the value of every cut.
Definition 2.2. A (1 ± )-cut sparsifier H of a graph G is a subgraph of G with weights wH such
that for every subset U ⊆ V
(1 − )wH (∂H (U )) ≤ wG (∂G (U )) ≤ (1 + )wH (∂H (U )) .

2.5

Sampling Schemes for Constructing Sparsifiers

Most efficient constructions of sparsifiers are randomized, partly because when G is the complete
graph, the resulting sparsifier needs to be an expander. These randomized schemes rely on importance
sampling, which for each edge:
1. Keeps it with probability pe ,
2. If the edge is kept, its weight is rescaled to

we
pe .

A crucial property of this process is that the edge’s expectation is preserved. As both cut and
spectral sparsifiers can be viewed as preserving sums over linear combinations of edge weights,
each of these terms have correct expectation. The concentration of such processes can then be
bounded using either matrix concentration bounds in the spectral case [Tro12, SS11], or a variety of
combinatorial arguments [BK15].
Our algorithms in this paper will use an even simpler version of this importance sampling scheme:
all of our pe ’s will be set to either 1 or 1/2. This scheme has a direct combinatorial interpretation:
1. Keep some of the edges.
2. Take a random half of the other edges, and double the weights of the edges kept.
Note that composing such a routine O(log n) times gives a sparsifier, as long as the part we keep is
small. So the main issue is to figure out how to get a small part to keep.

4

2.6

Spanning Trees and Spanners

A spanning forest F of G is a forest (i.e., acyclic graph) on a subset of the edges of G such that
every pair of vertices that is connected in G is also connected in F . A minimum/maximum spanning
forest is a spanning forest of minimum/maximum total weight.
For every pair of vertices u and v we denote by dG (u, v) the distance between u and v (i.e., the
length of the shortest path connecting u and v) in G with respect to the resistances. The graph
sparsification concept also exists with respect to distances in the graph. Such sparse subgraphs that
preserves distances approximately are called spanners.
Definition 2.3. A spanner of stretch α, or short α-spanner, (where α ≥ 1) of an undirected
(possibly weighted) graph G is a subgraph H of G such that, for every pair of vertices u and v,
dH (u, v) ≤ αdG (u, v).

3
3.1

Overview and Related Work
Dynamic Spectral Sparsifier

We first develop a fully dynamic algorithm for maintaining a spectral sparsifier of a graph with
polylogarithmic amortized update time.
Related Work. Spectral sparsifiers play important roles in fast numerical algorithms [BSS+ 13].
Spielman and Teng were the first to study these objects [ST11]. Their algorithm constructs a
(1 ± )-spectral sparsifier of size O(n · poly(log n, −1 )) in nearly linear time. This result has seen
several improvements in recent years [SS11, bHS16, Zou12, ZLO15]. The state of the art in the
sequential model is an algorithm by Lee and Sun [LS15] that computes a (1 ± )-spectral sparsifier of
size O(n−2 ) in nearly linear time. Most closely related to the data structural question are streaming
routines, both in one pass incremental [KL13], and turnstile [AGM13, KW14, KLM+ 14].
A survey of spectral sparsifier constructions is given in [BSS+ 13]. Many of these methods rely
on solving linear systems built on the graph, for which there approaches with a combinatorial
flavor using low-stretch spanning trees [KOS+ 13, LS13] and purely numerical solvers relying on
sparsifiers [PS14] or recursive constructions [KLP+ 16]. We build on the spectral sparsifier obtained
by a simple, combinatorial construction of Koutis [Kou14], which initially was geared towards
parallel and distributed implementations.
Sparsification Framework. In our framework we determine ‘sampleable’ edges by using spanners
to compute a set of edges of bounded effective resistance. From these edges we then sample by coin
flipping to obtain a (moderately sparser) spectral sparsifier in which the number of edges has been
reduced by a constant fraction. This step can then be iterated a small number of times in order to
compute the final sparsifier.
Concretely, we define a t-bundle spanner B = T1 ∪ · · · ∪ Tt (for a suitable, polylogarithmic, value
of t) as a sequence of spanners T1 , . . . , Tt where the edges of each spanner are removed from the
graph before computing the next spanner, i.e., T1 is a spanner of G, T2 is a spanner of G \ T1 , etc;
here each spanner has stretch O(log n). We then sample each non-bundle edge in G \ B with some
constant probability p and scale the edge weights of the sampled edges proportionally. The t-bundle
spanner serves as a certificate for small resistance of the non-bundle edges in G \ B as it guarantees
the presence of t disjoint paths of length at most the stretch of the spanner. Using this property
5

one can apply matrix concentration bounds [Tro12] to show the t-bundle together with the sampled
edges is a moderately sparse spectral sparsifier. We repeat this process of ‘peeling off’ a t-bundle
from the graph and sampling from the remaining edges until the graph is sparse enough (which
happens after a logarithmic number of iterations). Our final sparsifier consists of all t-bundles
together with the sampled edges of the last stage.
Towards a Dynamic Algorithm. To implement the spectral sparsification algorithm in the
dynamic setting we need to dynamically maintain a t-bundle spanner. Our approach to this problem
is to run t different instances of a dynamic spanner algorithm, in order to separately maintain a
S
spanner Ti for each graph Gi = G \ i−1
j=1 Tj , for 1 ≤ i ≤ t.
Baswana, Khurana, and Sarkar [BKS12] gave a fully dynamic algorithm for maintaining a
spanner of stretch O(log n) and size O(n log2 n) with polylogarithmic update time.1 A natural first
idea would be to use this algorithm in a black-box fashion in order to separately maintain each
spanner of a t-bundle. However, we do not know how to do this because of the following obstacle. A
single update in G might lead to several changes of edges in the spanner T1 , an average of Ω(log n)
according to the amortized upper bound. This means that the next instance of the fully dynamic
spanner algorithm which is used for maintaining T2 , not only has to deal with the deletion in G but
also the artificially created updates in G2 = G \ T1 . This of course propagates to more updates in all
graphs Gi . Observe also that any given update in Gt caused by an update in G, can be requested
repeatedly, as a result of subsequent updates in G. Without further guarantees, it seems that with
this approach we can only hope for an upper bound of O(logt−1 n) (on average) on the number
of changes to be processed for updating Gt after a single update in G. That is too high because
the sparsification algorithm requires us to take t = Ω(log n). Our solution to this problem lies in a
substantial modification of the dynamic spanner algorithm in [BKS12] outlined below.
Dynamic Spanners with Monotonicity. The spanner algorithm of Baswana et al. [BKS12] is
at its core a decremental algorithm (i.e., allowing only edge deletions in G), which is subsequently
leveraged into a fully dynamic algorithm by a black-box reduction. We follow the same approach by
first designing a decremental algorithm for maintaining a t-bundle spanner. This is achieved by
modifying the decremental spanner algorithm so that, in addition to its original guarantees, it has
the following monotonicity property:
Every time an edge is added to the spanner T , it stays in T until it is deleted from G.
Recall that we initially want to maintain a t-bundle spanner T1 , . . . , Tt under edge deletions
only. In general, whenever an edge is added to T1 , it will cause its deletion from the graph G \ T1
for which the spanner T2 is maintained. Similarly, removing an edge from T1 causes its insertion
into G \ T1 , unless the edge is deleted from G. This is precisely what the monotonicity property
guarantees: that an edge will not be removed from T1 unless deleted from G. The consequence is
that no edge insertion can occur for G2 = G \ T1 . Inductively, no edge is ever inserted into Gi , for
each i. Therefore the algorithm for maintaining the spanner Ti only has to deal with edge deletions
from the graph Gi , thus it becomes possible to run a different instance of the same decremental
spanner algorithm for each Gi . A single deletion from G can still generate many updates in the
1

More precisely, they gave two fully dynamic algorithms for maintaing a (2k − 1)-spanner for any integer k ≥ 2:
The first algorithm guarantees a spanner of expected size O(kn1+1/k log n) and has expected amortized update time
O(k2 log2 n) and the second algorithm guarantees a spanner of expected size O(k8 n1+1/k log2 n) and has expected
amortized update time O(7k/2 ).

6

bundle. But for each i, the instance of the dynamic spanner algorithm working on Gi can only
delete each edge once. Furthermore, we only run a small number t of instances. So the total number
of updates remains bounded, allowing us to claim the upper bound on the amortized update time.
In addition to the modification of the dynamic spanner algorithm, we have also deviated from
Koutis’ original scheme [Kou14] in that we explicitly ‘peel off’ each iteration’s bundle from the
graph. In this way we avoid that the t-bundles from different iterations share any edges, which
seems hard to handle in the decremental setting we ultimately want to restrict ourselves to.
The modified spanner algorithm now allows us to maintain t-bundles in polylogarithmic update
time, which is the main building block of the sparsifier algorithm. The remaining parts of the
algorithm, like sampling of the non-bundle edges by coin-flipping, can now be carried out in the
straightforward way in polylogarithmic amortized update time. At any time, our modified spanner
algorithm can work in a purely decremental setting. As mentioned above, the fully dynamic sparsifier
algorithm is then obtained by a reduction from the decremental sparsifier algorithm.

3.2

Dynamic Cut Sparsifier

We then give dynamic algorithms for maintaining a (1 ± )-cut sparsifier. We obtain a fully dynamic
algorithm with polylogarithmic worst-case update time by leveraging a recent worst-case update
time algorithm for dynamically maintaining a spanning tree of a graph [KKM13]. As mentioned
above, spectral sparsifiers are more general than cut sparsifiers. The big advantage of studying
cut sparsification as a separate problem is that we can achieve polylogarithmic worst-case update
time, where the update time guarantee holds for each individual update and is not amortized over a
sequence of updates.
Related Work. In the static setting, Benczúr and Karger [BK15] developed an algorithm for
computing a (1 ± )-cut sparsifier of size O(n · poly(log n, −1 )) in nearly linear time. Their approach
is to first compute a value called strength for each edge and then sampling each edge with probability
proportional to its strength. Their proof uses a cut-counting argument that shows that the majority
of cuts are large, and therefore less likely to deviate from their expectation. A union bound over
these (highly skewed) probabilities then gives the overall w.h.p. success bound. This approach was
refined by Fung et al. [FHH+ 11] who show that a cut sparsifier can also be obtained by sampling
each edge with probability inversely proportional to its (approximate) local edge connectivity, giving
slightly better guarantees on the sparsifier. The work of Kapron, King, and Mountjoy [KKM13]
contains a fully dynamic approximate “cut oracle” with worst-case update time O(log2 n). Given a
set U ⊆ V as the input of a query, it returns a 2-approximation to the number of edges in U × V \ U
in time O(|U | log2 n). The cut sparsifier question has also been studied in the (dynamic) streaming
model [AG09, AGM12a, AGM12b].
Our Framework. The algorithm is based on the observation that the spectral sparsification
scheme outlined above in Section 3.1. becomes a cut sparsification algorithm if we simply replace
spanners by maximum weight spanning trees (MSTs). This is inspired by sampling according to
edge connectivities; the role of the MSTs is to certify lower bounds on the edge connectivities. We
observe that the framework does not require us to use exact MSTs. For our t-bundles we can use a
relaxed, approximate concept that we call α-MST that. Roughly speaking, an α-MST guarantees a
‘stretch’ of α in the infinity norm and, as long as it is sparse, does not necessarily have to be a tree.

7

Similarly to before, we define a t-bundle α-MST B as the union of a sequence of α-MSTs T1 , . . . Tt
where the edges of each tree are removed from the graph before computing the next α-MST. The
role of α-MST is to certify uniform lower bounds on the connectivity of edges; these bounds are
sufficiently large to allow uniform sampling with a fixed probability.
This process of peeling and sampling is repeated sufficiently often and our cut sparsifier then
is the union of all the t-bundle α-MSTs and the non-bundle edges remaining after taking out the
last bundle. Thus, the cut sparsifier consists of a polylogarithmic number of α-MSTs and a few
(polylogarithmic) additional edges. This means that for α-MSTs based on spanning trees, our cut
sparsifiers are not only sparse, but also have polylogarithmic arboricity, which is the minimum
number of forests into which a graph can be partitioned.
Simple Fully Dynamic Algorithm. Our approach immediately yields a fully dynamic algorithm
by using a fully dynamic algorithm for maintaining a spanning forest. Here we basically have
two choices. Either we use the randomized algorithm of Kapron, King, and Mountjoy [KKM13]
with polylogarithmic worst-case update time. Or we use the deterministic algorithm of Holm, de
Lichtenberg, and Thorup [HLT01] with polylogarithmic amortized update time. The latter algorithm
is slightly faster, at the cost of providing only amortized update-time guarantees. A t-bundle 2-MST
can be maintained fully dynamically by running, for each of the log W weight classes of the graph, t
instances of the dynamic spanning tree algorithm in a ‘chain’.
An important observation about the spanning forest algorithm is that with every update in the
graph, at most one edge is changed in the spanning forest: If for example an edge is deleted from
the spanning forest, it is replaced by another edge, but no other changes are added to the tree.
S
Therefore a single update in G can only cause one update for each graph Gi = G \ i−1
j=1 Tj and Ti .
This means that each instance of the spanning forest algorithm creates at most one ‘artificial’ update
that the next instance has to deal with. In this way, each dynamic spanning forest instance used for
the t-bundle has polylogarithmic update time. As t = polylog n, the update time for maintaining a
t-bundle is also polylogarithmic. The remaining steps of the algorithm can be carried out dynamically
in the straightforward way and overall give us polylogarithmic worst-case or amortized update time.
A technical detail of our algorithm is that the high-probability correctness achieved by the
Chernoff bounds only holds for a polynomial number of updates in the graph. We thus have to
restart the algorithm periodically. This is trivial when we are shooting for an amortized update time.
For a worst-case guarantee we can neither completely restart the algorithm nor change all edges of
the sparsifier in one time step. We therefore keep two instances of our algorithm that maintain two
sparsifiers of two alternately growing and shrinking subgraphs that at any time partition the graph.
This allows us to take a blend of these two subgraph sparsifiers as our end result and take turns in
periodically restarting the two instances of the algorithm.

3.3

(1 − )-Approximate Undirected Bipartite Flow

We then study ways of utilizing our sparsifier constructions to give routines with truly sublinear
update times. The problem that we work with will be maintaining an approximate maximum
flow problem on a bipartite graph GA,B = (A, B, E) with demand −1 and 1 on each vertex in A
and B, respectively. All edges are unit weight and we dynamically insert and delete edges. The
maximum flow minimum cut theorem states that the objective here equals to the minimum s − t cut
or maximum s − t flow in G, which will be GA,B where we add vertices s and t, and connect each
vertex in A to s and each vertex in B to t. The only dynamic changes in this graph will be in edges

8

between A and B. As our algorithms builds upon cut sparsifiers, and flow sparsifiers [KLO+ 14] are
more involved, we will focus on only finding cuts.
This problem is motivated by the dynamic approximate maximum matching problem, which
differs in that the edges are directed, and oriented from A to B. This problem has received much
attention recently [OR10, BGS15, NS13, GP13, PS16, BS16], and led to the key definition of low
arboricity graphs [NS13, PS16]. On the other hand, bipartite graphs are known to be difficult to
sparsify: the directed reachability matrix from A to B can encode Θ(n2 ) bits of information. As a
result, we study the undirected variant of this problem instead, with the hope that this framework
can motivate other definitions of sparsification suitable for wider classes of graphs.
Another related line of work are fully dynamic algorithm for maintaining the global minimum
√
cut [Tho07, TK00] with update time O( n polylog n). As there are significant differences between
approximating global minimum cuts and st-minimum cuts in the static setting [Kar00], we believe
that there are some challenges to adapting these techniques for this problem. The data structure by
Thorup [Tho07] can either maintain global edge connectivity up to polylog n exactly or, with high
probability, arbitrary global edge connectivity with an approximation of 1 + o(1). The algorithms
also maintain concrete (approximate) minimum cuts, where in the latter algorithm the update time
√
increases to O( m polylog n) (and cut edges can be listed in time O(log n) per edge). Thorup’s
result was preceded by a randomized algorithm with worse approximation ratio for the global edge
√
connectivity by Thorup and Karger [TK00] with update time O( n polylog n).
At the start of Section 6 we will show that the problem we have formulated above is in fact
different from matching. On the other hand, our incorporation of sparsifiers for maintaining solutions
to this problem relies on several properties that hold in a variety of other settings:
1. The static version can be efficiently approximated.
2. The objective can be approximated via graph sparsifiers.
3. A small answer (for which the algorithm’s current approximation may quickly become suboptimal) means the graph also has a small vertex cover.
4. The objective does not change much per each edge update.
As with algorithms for maintaining high quality matchings [GP13, PS16], our approach aims to
get a small amortized cost by keeping the same minimum s − t cut for many consecutive dynamic
steps. Specifically, if we have a minimum s − t cut of size (2 + 2 )OP T , then we know this cut will
remain (2 + ) approximately optimal for 2 OP T dynamic steps. This allows us to only compute a
new minimum s − t cut every 2 OP T dynamic steps.
As checking for no edges would be an easy boundary case, we will assume throughout all the
analysis that OP T > 0. To obtain an amortized O(poly(log n, −1 )) update cost, it suffices for this
computation to take O(OP T · poly(log n, −1 )) time. In other words, we need to solve approximate
maximum flow on a graph of size O(OP T · poly(log n, −1 )). Here we incorporate sparsifiers using
the other crucial property used in matching data structures [OR10, GP13, PS16]: if OP T is small,
G also has a small vertex cover.
Lemma 3.1. The minimum vertex cover in G has size at most OP T + 2 where OP T is the size of
the minimum s − t cut in G.
We utilize the low arboricity of our sparsifiers to find a small vertex cover with the additional
property that all non-cover vertices have small degree. We will denote this (much) smaller set of
9

vertices as V C. In a manner similar to eliminating vertices in numerical algorithms [KLP+ 16], the
graph can be reduced to only edges on V C at the cost of a (2 + )-approximation. Maintaining a
sparsifier of this routine again leads to an overall routine that maintains a (2 + )-approximation in
polylog n time per update, which we show in Section 6.
Sparsifying vertices instead of edges inherently implies that an approximation of all cut values
cannot be maintained. Instead, the sparsifier, which will be referred to as a terminal-cut-sparsifier,
maintains an approximation of all minimum cuts between any two terminal vertices, where the
vertex cover is the terminal vertex set for our purposes. More specifically, given a minimum cut
between two terminal vertices on the sparsified graph, by adding each independent vertex from the
original graph to the cut set it is more connected to, an approximate minimum cut on the original
graph is achieved. This concept of terminal-cut-sparsifier will be equivalent to that in [AGK14],
and will be given formal treatment in Section 8.
The large approximation ratio motivated us to reexamine the sparsification routines, namely the
one of reducing the graph to one whose size is proportional to |V C|. This is directly related to the
terminal cut sparsifiers studied in [AGK14, KK15]. However, for an update time of poly(log n, −1 ),
it is crucial for the vertex sparsifier to have size O(|VC| poly(log n, −1 )). As a result, instead of
doing a direct union bound over all 2|VC| cuts to get a size of poly(|VC|) as in [AGK14], we need to
invoke cut counting as with cut sparsifier constructions. This necessitates the use of objects similar
to t-bundles to identify edges with small connectivity. This leads to a sampling process motivated
by the (2 + )-approximate routine, but works on vertices instead of edges.
By relating the processes, we are able to absorb the factor 2 error into the sparsifier size. In
Section 7, we formalize this process, as well as its guarantees on graphs with bounded weights. Here
a major technical challenge compared to analyses of cut sparsifiers [FHH+ 11] is that the natural
scheme of bucketing by edge weights is difficult to analyze because a sampled vertex could have
non-zero degree in multiple buckets. We work around this issue via a pre-processing scheme on G
that creates an approximation so that all vertices outside of VC have degree polylog n. This scheme
is motivated in part by the weighted expanders constructions from [KLP+ 16]. Bucketing after this
processing step ensures that each vertex belongs to a unique bucket. In terms of a static sparsifier
on terminals, the result that is most comparable to results from previous works is:
Corollary 3.2. Given any graph G = (V, E), and a vertex cover VC of G, where X = V \ VC,
with error , we can build an -approximate terminal-cut-sparsifier H with O(|VC| poly(log n, −1 ))
vertices in O(m · poly(log n, −1 )) work.
Turning this into a dynamic routine leads to the result described in Theorem 1.3: a (1 + )approximate solution that can be maintained in time polylog(n) per update. It is important to note
that Theorem 1.2 plays an integral role in extending Corollary 3.2 to a dynamic routine, particularly
the low arboricity property that allows us to maintain a small vertex cover such that all non-cover
vertices have low degree. These algorithmic extensions, as well as their incorporation into data
structures are discussed in Section 8.

3.4

Discussion

Graph Sparsification. We use a sparsification framework in which we ‘peel off’ bundles of
sparse subgraphs to determine ‘sampleable’ edges, from which we then sample by coin flipping.
This leads to combinatorial and surprisingly straightforward algorithms for maintaining graph
sparsifiers. Additionally, this gives us low-arboricity sparsifiers; a property that we exploit for our
main application.
10

Although spectral sparsification is more general than cut sparsification. Our treatment of cut
sparsification has two motivations. First, we can obtain stronger running time guarantees. Second,
our sparsifier for the (1 − )-approximate maximum flow algorithm on bipartite graphs hinges upon
improved routines for vertex sparsification, a concept which leads to different objects in the spectral
setting.
Dynamic Graph Algorithms. In our sparsification framework we sequentially remove bundles
of sparse subgraphs to determine ‘sampleable’ edges. This leads to ‘chains’ of dynamic algorithms
where the output performed by one algorithm might result in updates to the input of the next
algorithm. This motivates a more fine-grained view on of dynamic algorithms with the goal of
obtaining strong bounds on the number of changes to the output.
Future Work. The problem whether spectral sparsifiers can be maintained with polylogarithmic
worst-case update time remains open. Our construction goes via spanners and therefore a natural
question is whether spanners can be maintained with worst-case update time. Maybe there are also
other more direct ways of maintaining the sparsifier. A more general question is whether we can
find more dynamic algorithms for numerical problems.
Our dynamic algorithms cannot avoid storing the original graph, which is undesirable in terms
of space consumption. Can we get space-efficient dynamic algorithms without sacrificing fast update
time?
The sparsification framework for peeling off subgraphs and uniformly sampling from the remaining
edges is very general. Are there other sparse subgraphs we could start with in the peeling process?
Which properties do the sparsifiers obtained in this way have? In particular, it would be interesting
to see whether our techniques can be generalized to flow sparsifiers [KLO+ 14, AGK14].
The combination of sparsifiers with density-sensitive approaches for dynamic graph data structures [NS13, PS16] provides an approach for obtaining poly(log, −1 ) update times. We believe this
approach can be generalized to other graph cut problems. In particular, the flow networks solved
for balanced cuts and graph partitioning are also bipartite and undirected, and therefore natural
directions for future work.

4

Dynamic Spectral Sparsifier

In this section we give an algorithm for maintaining a spectral sparsifier under edge deletions and
insertions with polylogarithmic amortized update time. The main result of this section is as follows.
Theorem 4.1. There exists a fully dynamic randomized algorithm with polylogarithmic update time
for maintaining a (1 ± )-spectral sparsifier H of a graph G, with probability at least 1 − 1/nc for
any 0 <  ≤ 1 and c ≥ 1. Specifically, the amortized update time of the algorithm is
O(c−2 log3 ρ log6 n)
and the size of H is
O(cn−2 log3 ρ log5 n log W + mρ−1 ) ,
where 1 ≤ ρ ≤ m is a parameter of choice. Here, W is the ratio between the largest and the smallest
edge weight in G. The ratio between the largest and the smallest edge weight in H is at most O(nW ).

11

After giving an overview of our algorithm, we first explain our spectral sparsification scheme in
a static setting and prove its properties. Subsequently, we show how we can dynamically maintain
the edges of such a sparsifier by making this scheme dynamic.

4.1

Algorithm Overview

Sparsification Framework. In our framework we determine ‘sampleable’ edges by using spanners
to compute a set of edges of bounded effective resistance. From these edges we then sample by coin
flipping to obtain a (moderately sparser) spectral sparsifier in which the number of edges has been
reduced by a constant fraction. This step can then be iterated a small number of times in order to
compute the final sparsifier.
Concretely, we define a t-bundle spanner B = T1 ∪ · · · ∪ Tt (for a suitable, polylogarithmic, value
of t) as a sequence of spanners T1 , . . . , Tt where the edges of each spanner are removed from the
graph before computing the next spanner, i.e., T1 is a spanner of G, T2 is a spanner of G \ T1 , etc;
here each spanner has stretch O(log n). We then sample each non-bundle edge in G \ B with some
constant probability p and scale the edge weights of the sampled edges proportionally. The t-bundle
spanner serves as a certificate for small resistance of the non-bundle edges in G \ B as it guarantees
the presence of t disjoint paths of length at most the stretch of the spanner. Using this property
one can apply matrix concentration bounds to show the t-bundle together with the sampled edges
is a moderately sparse spectral sparsifier. We repeat this process of ‘peeling off’ a t-bundle from
the graph and sampling from the remaining edges until the graph is sparse enough (which happens
after a logarithmic number of iterations). Our final sparsifier consists of all t-bundles together with
the sampled edges of the last stage.
Towards a Dynamic Algorithm. To implement the spectral sparsification algorithm in the
dynamic setting we need to dynamically maintain a t-bundle spanner. Our approach to this problem
is to run t different instances of a dynamic spanner algorithm, in order to separately maintain a
S
spanner Ti for each graph Gi = G \ i−1
j=1 Tj , for 1 ≤ i ≤ t.
Baswana, Khurana, and Sarkar [BKS12] gave a fully dynamic algorithm for maintaining a
spanner of stretch O(log n) and size O(n log2 n) with polylogarithmic update time.2 A natural first
idea would be to use this algorithm in a black-box fashion in order to separately maintain each
spanner of a t-bundle. However, we do not know how to do this because of the following obstacle. A
single update in G might lead to several changes of edges in the spanner T1 , an average of Ω(log n)
according to the amortized upper bound. This means that the next instance of the fully dynamic
spanner algorithm which is used for maintaining T2 , not only has to deal with the deletion in G but
also the artificially created updates in G2 = G \ T1 . This of course propagates to more updates in all
graphs Gi . Observe also that any given update in Gt caused by an update in G, can be requested
repeatedly, as a result of subsequent updates in G. Without further guarantees, it seems that with
this approach we can only hope for an upper bound of O(logt−1 n) (on average) on the number
of changes to be processed for updating Gt after a single update in G. That is too high because
the sparsification algorithm requires us to take t = Ω(log n). Our solution to this problem lies in a
substantial modification of the dynamic spanner algorithm in [BKS12] outlined below.
2
More precisely, they gave two fully dynamic algorithms for maintaing a (2k − 1)-spanner for any integer k ≥ 2:
The first algorithm guarantees a spanner of expected size O(kn1+1/k log n) and has expected amortized update time
O(k2 log2 n) and the second algorithm guarantees a spanner of expected size O(k8 n1+1/k log2 n) and has expected
amortized update time O(7k/2 ).

12

Dynamic Spanners with Monotonicity. The spanner algorithm of Baswana et al. [BKS12] is
at its core a decremental algorithm (i.e., allowing only edge deletions in G), which is subsequently
leveraged into a fully dynamic algorithm by a black-box reduction. We follow the same approach by
first designing a decremental algorithm for maintaining a t-bundle spanner. This is achieved by
modifying the decremental spanner algorithm so so that, additional to its original guarantees, it has
the following monotonicity property:
Every time an edge is added to the spanner T , it stays in T until it is deleted from G.
Recall that we initially want to maintain a t-bundle spanner T1 , . . . , Tt under edge deletions
only. In general, whenever an edge is added to T1 , it will cause its deletion from the graph G \ T1
for which the spanner T2 is maintained. Similarly, removing an edge from T1 causes its insertion
into G \ T1 , unless the edge is deleted from G. This is precisely what the monotonicity property
guarantees: that an edge will not be removed from T1 unless deleted from G. The consequence is
that no edge insertion can occur for G2 = G \ T1 . Inductively, no edge is ever inserted into Gi , for
each i. Therefore the algorithm for maintaining the spanner Ti only has to deal with edge deletions
from the graph Gi , thus it becomes possible to run a different instance of the same decremental
spanner algorithm for each Gi . A single deletion from G can still generate many updates in the
bundle. But for each i the instance of the dynamic spanner algorithm working on Gi can only delete
each edge once. Furthermore, we only run a small number t of instances. So the total number of
updates remains bounded, allowing us to claim the upper bound on the amortized update time.
In addition to the modification of the dynamic spanner algorithm, we have also deviated from
Koutis’ original scheme [Kou14] in that we explicitly ‘peel off’ each iteration’s bundle from the
graph. In this way we avoid that the t-bundles from different iterations share any edges, which
seems hard to handle in the decremental setting we ultimately want to restrict ourselves to.
The modified spanner algorithm now allows us to maintain t-bundles in polylogarithmic update
time, which is the main building block of the sparsifier algorithm. The remaining parts of the
algorithm, like sampling of the non-bundle edges by coin-flipping, can now be carried out in the
straightforward way in polylogarithmic amortized update time. At any time, our modified spanner
algorithm can work in a purely decremental setting. As mentioned above, the fully dynamic sparsifier
algorithm is then obtained by a reduction from the decremental sparsifier algorithm.

4.2

Spectral Sparsification

As outlined above, iteratively ‘peels off’ bundles of spanners from the graph.
Definition 4.2. A t-bundle α-spanner (where t ≥ 1, α ≥ 1) of an undirected graph G is the union
S
T = ki=1 Ti of a sequence of graphs T1 , . . . , Tk such that, for every 1 ≤ i ≤ k, Ti is an α-spanner of
Si−1
G \ j=1 Tj .
The algorithm for spectral sparsification is presented in Figures 1 and 2. Algorithm LightSpectral-Sparsify computes a moderately sparser (1±)-spectral sparsifier. Algorithm SpectralSparsify takes a parameter ρ and computes the sparsifier in k = dlog ρe iterations of LightSpectral-Sparsify.
We will now prove the properties of these algorithms. We first need the following lemma that
shows how t-bundle spanners can be used to bound effective resistances. We highlight the main
intuition of this crucial observation in our proof sketch.

13

Light-Spectral-Sparsify (G, )
1. t ← d12(c + 1)α−2 ln ne for some absolute constant c.
2. let B =

St

j=1 Tj

be a t-bundle α-spanner of G

3. H := B
4. for each edge e ∈ G \ B
(a) with probability 1/4: add e to H with wH (e) ← 4wG (e)
5. return (H, B)

Figure 1: Light-Spectral-Sparsify (G, c, ). We give a dynamic implementation of this algorithm
in Section 4.4.2. In particular we dynamically maintain the t-bundle α-spanner B which results in a
dynamically changing graph G \ B.

Spectral-Sparsify (G, c, )
1. k ← dlog ρe
2. G0 ← G
3. B0 ← (V, ∅)
4. for i = 1 to k
(a) (Hi , Bi ) ← Light-Spectral-Sparsify(Gi−1 , c, /(2k))
(b) Gi ← Hi \ Bi
(c) if Gi has less than (c + 1) ln n edges then break
5. H ←

S

1≤j≤i Bj

(* break loop *)

∪ Gi

6. return (H, {Bj }ij=1 , Gi )

Figure 2: Spectral-Sparsify (G, c, ). We give a dynamic implementation of this algorithm in
Section 4.4.3. In particular we dynamically maintain each Hi and Bi as the result of a dynamic
implementation of Light-Spectral-Sparsify which results in dynamically changing graphs Gi .

14

Lemma 4.3 ([Kou14]). Let G be a graph and B be a t-bundle α-spanner of G. For every edge e of
G \ B, we have
α
wG (e) · RG (e) ≤
t
which implies that
α
wG (e) · Le  · LG
t
where Le is the n × n Laplacian of the unweighted edge e.
Sketch. Fix some edge e = (u, v) of G \ B and let T1 , . . . Tt denote the (pairwise disjoint) α-spanners
contained in B. For every 1 ≤ i ≤ t, let πi denote the shortest path from u to v in Ti . The length of
S
the path π in Ti exceeds the distance from u to v in G \ i−1
j=1 Tj by at most a factor of α (property
of the spanner Ti ). Since e is contained in G \ B, the latter distance is at most the resistance of the
edge e as we have defined distances as the length of shortest paths with respect to the resistances of
the edges.
Consider each path πi as a subgraph of G and let Π be the subgraph consisting of all paths πi .
Observe that Π consists of a parallel composition of paths, which in turn consists of a serial
composition of edges, the we can view as resistors. We can now apply the well-known rules for serial
and parallel composition for computing effective resistances and get the desired bounds.
Our second tool in the analysis the following variant [Har12] of a matrix concentration inequality
by Tropp [Tro12].
Theorem 4.4. Let Y1 , . . . , Yk be independent positive semi-definite matrices of size n × n. Let
P
Y = ki=1 Yi and Z = E [Y ]. Suppose Yi  RZ, where R is a scalar, for every 1 ≤ i ≤ k. Then for
all  ∈ [0, 1]
P

" k
X

#

Yi  (1 − )Z ≤ n · exp(−2 /2R)

i=1

P

" k
X

#

Yi  (1 + )Z ≤ n · exp(−2 /3R)

i=1

Given these facts we can now prove the following Lemma which is a slight generalization of a
Lemma in [Kou14]. As the proof is quite standard we have moved it to Appendix A (together with
the proofs of the subsequent two lemmas). For applying the lemma in our dynamic algorithm it
is crucial that the input graph (which might be generated by another randomized algorithm) is
independent of the random choices of algorithm Light-Spectral-Sparsify.
Lemma 4.5. The output H of Light-Spectral-Sparsify is a (1 ± )-spectral sparsifier with
probability at least 1 − n−(c+1) for any input graph G that is independent of the random choices of
the algorithm.
By iteratively applying the sparsification of Light-Spectral-Sparsify as done in SpectralSparsify we obtain sparser and sparser cut sparsifiers.
Lemma 4.6. The output H of algorithm Spectral-Sparsify is a (1 ± )-spectral sparsifier with
probability at least 1 − 1/nc+1 for any input graph G that is independent of the random choices of
the algorithm.

15

Lemma 4.7. With probability at least 1−2n−c , the number of iterations before algorithm SpectralSparsify terminates is
min{dlog ρe, dlog m/((c + 1) log n)e}.
Moreover the size of H is


O


X

|Bi | + m/ρ + c log n ,

1≤j≤i

and the size of the third output of the graph is at most max{O(c log n), O(m/ρ)}.
We conclude that with probability at least 1 − n−c our construction yields a (1 ± )-spectral
sparsifier that also has the properties of Lemma 4.7.
Typically, the t-bundle spanners will consist of a polylogarithmic number of spanners of size
O(n poly log n) and thus the resulting spectral sparsifier will have size O(n poly log n, −1 + m/ρ).
In each of the at most log n iterations the weight of the sampled edges is increased by a factor of
4. Thus, the ratio between the largest and the smallest edge weight in H is at most by a factor of
O(n) more than in G, i.e., O(nW ).

4.3

Decremental Spanner with Monotonicity Property

We first develop the decremental spanner algorithm, which will give us a (log n)-spanner of size
O(n poly (log n)) with a total update time of O(m poly (log n)). Our algorithm is a careful modification of the dynamic spanner algorithm of Baswana et al. [BKS12] having the following additional
monotonicity property: Every time an edge is added to H, it stays in H until it is deleted from G
by the adversary. Formally, we will prove the following theorem.
Lemma 4.8. For every k ≥ 2 and every 0 <  ≤ 1, there is a decremental algorithm for maintaining
a (1 + )(2k − 1)-spanner H of expected size O(k 2 n1+1/k log n log1+ W ) for an undirected graph G
with non-negative edge weights that has an expected total update time of O(k 2 m log n), where W
is the ratio between the largest and the smallest edge weight in G. Additional H has the following
property: Every time an edge is added to H, it stays in H until it is deleted from G. The bound on
the expected size and the expected running time hold against an oblivious adversary.
It would be possible to enforce the monotonicity property for any dynamic spanner algorithm
by simply overriding the algorithms’ decision for removing edges from the spanner before they are
deleted from G. Without additional arguments however, the algorithm’s bound on the size of the
spanner might then not hold anymore. In particular, we do not know how obtain a version of the
spanner of Baswana et al. that has the monotonicity property without modifying the internals of
the algorithm.
Similar to Baswana et al. [BKS12] we actually develop an algorithm for unweighted graphs and
then extend it to weighted graphs as follows. Let W be the ratio of the largest to the smallest edge
weight in G. Partition the edges into log1+ W subgraphs based on their weights and maintain a
(2k − 1)-spanner ignoring the weights. The union of these spanners will be a (1 + )(2k − 1)-spanner
of G and the size increases by a factor of log1+ W compared to the unweighted version. The update
time stays the same as each update in the graph is performed only in one of the log1+ W subgraphs.
Therefore we assume in the following that G is an unweighted graph.

16

4.3.1

Algorithm and Running Time

We follow the approach of Baswana et al. and first explain how to maintain a clustering of the
vertices and then define our spanner using this clustering.
Clustering. Consider an unweighted undirected graph G = (V, E) undergoing edge deletions. Let
S ⊆ V be a subset of the vertices used as cluster centers. Furthermore, consider a permutation σ
on the set of vertices V and an integer i ≥ 0.
The goal is to maintain a clustering CS,σ,i consisting of disjoint clusters with one cluster
CS,σ,i [s] ⊆ V for every s ∈ S. Every vertex within distance i to the vertices in S is assigned to
the cluster of its closest vertex in S, where ties are broken according to the permutation σ. More
formally, v ∈ CS,σ,i [s] if and only if
• dG (v, s) ≤ i and
• for every s0 ∈ S \ {s} either
– dG (v, s) < dG (v, s0 ) or
– dG (v, s) = dG (v, s0 ) and σ(s) < σ 0 (s).
Observe that each cluster CS,σ,i [s] of a vertex s ∈ S can be organized as a tree consisting of
shortest paths to s. We demand that in this tree every vertex v chooses the parent that comes first
in the permutation σ among all candidates (i.e., among the vertices that are in the same cluster
Ci [s] as v and that are at distance d(v, s) − 1 from s).3 These trees of the clusters define a forest
FS,σ,i that we wish to maintain together with the clustering CS,σ,i .
Using a modification of the Even-Shiloach algorithm [ES81] all the cluster trees of the clustering
Ci together can be maintained in total time O(im log n).
Theorem 4.9 ([BKS12]). Given a graph G = (V, E), a set S ⊆ V , a random permutation σ of V ,
and an integer i ≥ 0, there is a decremental algorithm for maintaining the clustering CS,σ,i and the
corresponding forest FS,σ,i of partial shortest path trees from the cluster centers in expected total
time O(mi log n).
Note that we deviate from the original algorithm of Baswana et al. by choosing the parent in
the tree of each cluster according to the random permutation. In the algorithm of Baswana et al.
the parents in these trees were chosen arbitrarily. However, it can easily be checked that running
time guarantee of Theorem 4.9 also holds for our modification.
The running time analysis of Baswana et al. hinges on the fact that the expected number of
times a vertex changes its cluster is O(i log n).
Lemma 4.10 ([BKS12]). For every vertex v the expected number of times v changes its cluster in
CS,σ,i is at most O(i log n).
By charging time O(deg(v)) to every change of the cluster of v and every increase of the distance
from v to S (which happens at most i times), Baswana et al. get a total update time of O(im log n)
over all deletions in G. For our version of the spanner that has the monotonicity property we
additionally need the following observation whose proof is similar to the one of the lemma above.
3

Using the permutation to choose a random parent is not part of the original construction of Baswana et al.

17

Lemma 4.11. For every vertex v the expected number of times v changes its parent in FS,σ,i is at
most O(i log n).
Proof. Remember that we assume the adversary to be oblivious, which means that the sequence of
deletions is independent of the random choices of our algorithm. We divide the sequence of deletions
into phases. For every 1 ≤ l ≤ i the l-th phase consists of the (possibly empty) subsequence of
deletions during which the distance from v to S is exactly l, i.e., dG (v, S) = l.
Consider first the case l ≥ 2. We will argue about possible ‘configurations’ (s, u) such that v is in
the cluster of s and u is the parent of v that might occur in phase l. Let (s1 , u1 ), (s2 , u2 ), . . . , (st(l) , ut(l) )
(where t(l) ≤ n2 ) be the sequence of all pairs of vertices such that, at the beginning of phase l,
for every 1 ≤ j ≤ t(l) , sj is at distance l from v and uj is a neighbor of v. The pairs (si , ui ) in
this sequence are ordered according to the point in phase l at which they cease to be possible
configurations, i.e., at which either the distance of si to v increases to more than l or u is not a
neighbor of v anymore.
(l)
Let Aj denote the event that, at some point during phase l, v is in the cluster of sj and uj
is the parent of v. The expected number of times v changes its parent in FS,σ,i during phase l is
(l)
(l)
equal to the expected number of j’s such that event Aj takes place. Let Bj denote the event
that (sj , uj ) is lexicographically first among all pairs (sj , uj ), . . . , (st , ut(l) ) under the permutation
0
(l)
0
0
0
σ, i.e., hfor all
i j ≤h j ≤
i t either σ(sj ) ≤ σ(sj ) or σ(sj ) = σ(sj ) and σ(uj ), σ(uj ). Observe
(l)
(l)
(l)
(l)
that P Aj ≤ P Bj because the event Aj can only take place if the event Bj takes place.
h

(l)

i

Furthermore, P Bj = 1/(t(l) − j + 1) as every pair of (distinct) vertices has the same probability
of being first in the lexicographic order induced by σ. Thus, by linearity of expectation, the number
of times v changes its parent in FS,σ,i during phase l is at most
(l)

t
X
j=1

(l)

h

P

(l)
Aj

i

≤

t
X
j=1

(l)

h

P

(l)
Bj

i

(l)

t
X

t
X
1
1
=
=
= O(log t(l) ) = O(log n) .
(l)
j
t
−
j
+
1
j=1
j=1

In the second case l = 1, a slightly simpler argument bounds the number of times v changes its
parent (which is equal to the number of times v changes its cluster) by ordering the neighbors of v
in the order of deleting their edge to v. This is the original argument of Baswana et al. [BKS12] of
Lemma 4.10. We therefore also get that the number of times v changes its parent in FS,σ,i in phase
1 is at most O(log n).
We now sum up the expected number of changes during all phases, and, by linearity of expectation,
get that the number of times v changes its parent in FS,σ,i is at most O(i log n).
Spanner. Let 2 ≤ k ≤ log n be a parameter of the algorithm. At the initialization, we first create
a sequence of sets V = S0 ⊇ S1 ⊇ . . . ⊇ Sk = ∅ by obtaining Si+1 from sampling each vertex of Si
with probability n−1/k . Furthermore, we pick a random permutation σ of the vertices in V .
We use the algorithm of Theorem 4.9 to maintain, for every 1 ≤ i ≤ k, the clustering Ci := CSi ,σ
together with the forest Fi := FSi ,σ . Define the set Vi as Vi = {v ∈ V | dG (v, Si ) ≤ i}, i.e., the
set of vertices that are at distance at most i to some vertex of Si . Observe that the vertices in Vi
are exactly those vertices that are contained in some cluster Ci [s] of the clustering Ci . For every
vertex v ∈ Vi (where Ci [s] is the cluster of v) we say that a cluster Ci [s0 ] (for some s0 ∈ Si \ {s}) is
neighboring to v if G contains an edge (v, v 0 ) such that v 0 ∈ Ci [s0 ].
Our spanner H consists of the following two types of edges:

18

1. For every 1 ≤ i ≤ k, H contains all edges of the forest Fi consisting of partial shortest path
trees from the cluster centers.
2. For every 1 ≤ i ≤ k, every vertex v ∈ Vi \ Vi+1 (contained in some cluster Ci [s]), and every
neighboring cluster Ci [s0 ] of v, H contains one edge to Ci [s0 ], i.e., one edge (v, v 0 ) such that
v 0 ∈ Ci [s0 ].
The first type of edges can be maintained together with the spanning forests of the clustering
algorithm of Theorem 4.9. The second type of edges can be maintained with the following update
rule: Every time the clustering of a vertex v ∈ Vi \ Vi+1 changes, we add to H one edge to each
neighboring cluster. Every time such a ‘selected’ edge is deleted from G, we replace it with another
edge to this neighboring cluster until all of them are used up.
We now enforce the monotonicity property mentioned above in the straightforward way. Whenever we have added an edge to H, we only remove it again from H when it is also deleted from G.
We argue below that this makes the size of the spanner only slightly worse than in the original
construction of Baswana et al.
4.3.2

Stretch and Size

We now prove the guarantees on the stretch and size of H. The stretch argument is very similar to
the ones of Baswana et al. We include it here for completeness. In the stretch argument we need
stronger guarantees than Baswana et al. as we never remove edges from H, unless they are deleted
from G as well.
Lemma 4.12 ([BKS12]). H is a (2k − 1)-spanner of G.
Proof. Consider any edge (u, v) of the current graph G and the first j such that u and v are both
contained in Vj and at least one of u or v is not contained in Vj+1 . Without loss of generality
assume that u ∈
/ Vj+1 . Since v ∈ Vj , we know that v is contained in some cluster Cj [s] and because
of the edge (u, v) this cluster is neighboring to u. Similarly, the cluster of u is neighboring to v.
Consider the vertex out of u and v that has changed its cluster within Ci most recently (or take any
of the two if both of them haven’t changed their cluster since the initialization). Assume without
loss of generality that this vertex was u. Then Ci [s] has been a neighboring cluster of u at the time
the cluster of u changed, and thus, the spanner H contains some edge (u, v 0 ) such that v 0 ∈ Cj [s].
Using the cluster tree of Cj [s] we find a path from v 0 to v via s of length at most 2i in H. Thus, H
contains a path from u to v of length at most 2i + 1 ≤ 2k − 1 as desired.
Lemma 4.13. The number of edges of H is O(k 2 n1+1/k log n) in expectation.
Proof. Consider the first type of edges which are the ones stemming from the partial shortest path
trees from the cluster centers. We charge to each vertex v a total of O(k 2 log n) edges given by
all of v’s parents in the partial shortest path trees from the cluster centers over the course of the
algorithm. For every 1 ≤ i ≤ k, we know by Lemma 4.11 that the parent of v in Fi changes at most
O(i log n) times in expectation, which gives an overall bound of O(k 2 log n).
We get the bound on the second type of edges by charging to each vertex v a total of
O(k 2 n1/k log n) edges. Consider a vertex v ∈ Vi \ Vi+1 for some 0 ≤ i ≤ k − 1. The number
of neighboring clusters of v is equal to the number of vertices of Si that are at distance exactly
i + 1 from v. Since v ∈
/ Vi+1 the number of such vertices is n1/k in expectation. Thus, whenever
a vertex v ∈ Vi \ Vi+1 changes its cluster in Ci we can charge n1/k to vi to pay for the n1/k edges
19

to neighboring clusters. As v changes its cluster in Ci O(i log n) times by Lemma 4.10 and there
are k clusterings, the total number of edges of the second type contained in H is O(k 2 n1+1/k log n).
Note that are allowed to multiply the two expectations because the random variables in question
are independent.
The overall bound of O(k 2 n1+1/k log n) on the expected number of edges follows from the linearity
of expectation.

4.4

Decremental Spectral Sparsifier

In the following we explain how to obtain a decremental algorithm for maintaining a spectral
sparsifier using the template of Section 4.2. Internally we use our decremental spanner algorithm of
Section 4.3. It is conceptually important for our approach to first develop a decremental algorithm,
that is turned into a fully dynamic algorithm in Section 4.5. We follow the template of Section 4.2 by
first showing how to maintain t-bundle spanners under edge deletions, and then giving decremental
implementations of Light-Cut-Sparsify and Cut-Sparsify.
The overall algorithm will use multiple instances of the dynamic spanner algorithm, where
outputs of one instance will be used as the input of the next instance. We will do so in a strictly
hierarchical manner which means that we can order the instances in a way such that the output
of instance i only affects instances i + 1 and above. In this way it is guaranteed that the updates
made to instance i are independent of the internal random choices of instance i, which means that
each instance i is running in the oblivious-adversary setting required for Section 4.3.
4.4.1

Decremental t-Bundle Spanners

We first show how to maintain a t-bundle log n-spanner under edge deletions for some parameter t.
Using the decremental spanner algorithm of Lemma 4.8 with k = b(log n)/4c and  = 1 we maintain
S
a sequence H1 , . . . Ht of log n-spanners by maintaining Hi as the spanner of G \ 1≤j≤i−1 Hj . Here
we have to argue that this is legal in the sense that every instance of the algorithm of Lemma 4.8 is
run on a graph that only undergoes edge deletions.
Lemma 4.14. If no edges are ever inserted into G after the initialization, then this also holds for
S
G \ 1≤j≤i−1 Hj for every 1 ≤ i ≤ t + 1.
Proof. The proof is by induction on i. The claim is trivially true for i = 1 by the assumption that
there are only deletions in G. For i ≥ 2 we the argument uses the monotonicity property of the
dynamic algorithm for maintaining the spanner Hi−1 . By the induction hypothesis we already know
S
that no edges are ever added to the graph G \ 1≤j≤i−2 Hj . Therefore the only possibility of an
S
edge being added to G \ 1≤j≤i−1 Hj would be to remove an edge e from Hi−1 . However, by the
monotonicity property, when e is removed from Hi−1 , it is also deleted from G. Thus, e will not be
S
inserted into G \ 1≤j≤i−2 Hj .
S

Our resulting t-bundle log n-spanner then is B = 1≤i≤t Hi , the union of all these spanners.
Since the Hi0 s are disjoint the edges of B can be maintained in the obvious way by observing all
changes to the Hi0 s. By our choice of parameters, n1/k = O(1) and thus the expected size of B is
O(tn log2 n log W ). Observe that Lemma 4.14 implies that no edges will ever be inserted into the
complement G \ B, which will be relevant for our application in the spectral sparsifier algorithm.
We can summarize the guarantees of our decremental t-bundle spanner algorithm as follows.

20

Lemma 4.15. For every t ≥ 1, there is a decremental algorithm for maintaining a t-bundle log nspanner B of expected size O(tn log2 n log W ) for an undirected graph G with non-negative edge
weights that has an expected total update time of O(tm log3 n), where W is the ratio between the
largest and the smallest edge weight in G. Additional B has the following property: After the
initialization, no edges are ever inserted into the graph G \ B. The bound on the expected size and
the expected running time hold against an oblivious adversary.
4.4.2

Dynamic Implementation of Light-Spectral-Sparsify

We now show how to implement the algorithm Light-Spectral-Sparsify decrementally for a
graph G undergoing edge deletions.
For this algorithm we set t = d12(c + 3)α−2 ln ne. Note that this value is slightly larger than
the one proposed in the static pseudocode of Figure 1. For the sparsification proof in Section 4.2 we
have to argue that by our choice of t certain events happen with high probability. In the dynamic
algorithm we need ensure the correctness for up to n2 versions of the graph, one version for each
deletion in the graph. By increasing the multiplicative constant in t by 2 (as compared to the static
proof of Section 4.2) all desired events happen with high probability for all, up to n2 , versions of
the graph by a union bound.
The first ingredient of the algorithm is to maintain a t-bundle log n-spanner B of G under
edge deletions using the algorithm of Lemma 4.15. We now explain how to maintain a graph H 0 –
with the intention that H 0 contains the sampled non-bundle edges of G \ B – as follows: At the
initialization, we determine the graph H 0 by sampling each edge of G \ B with probability 1/4 and
adding it to H 0 with weight 4wG (e). We then maintain H 0 under the edge deletions in G using the
following update rules:
After every deletion in G we first propagate the update to the algorithm for maintaining the
t-bundle spanner B, possibly changing B to react to the deletion. We then check whether the
deletion in G and the change in B cause an deletion in the complement graph G \ B. Whenever
an edge e is deleted from G \ B, it is removed from H 0 . Note that by Lemma 4.15 no edge is ever
inserted into G \ B. We now simply maintain the graph H as the union of B and H 0 and make it
the first output of our algorithm; the second output is B.
By the update rules above (and the increased value of t to accommodate for the increased
number of events), this decremental algorithm imitates the static algorithm of Figure 1 and for
the resulting graph H we get the same guarantees as in Lemma 4.5. The total update time of our
decremental version of Light-Spectral-Sparsify is O(tm log3 n), as it is dominated by the time
for maintaining the t-bundle log n-spanner B.
As an additional property we get that no edge is ever added to the graph H 0 = H \B. Furthermore,
for all edges added to H 0 weights are always increased by the same factor. Therefore the ratio
between the largest and the smallest edge weight in H 0 will always be bounded by W , which is the
value of this quantity in G (before the first deletion).
4.4.3

Dynamic Implementation of Spectral-Sparsify

Finally, we show how to implement the algorithm Spectral-Sparsify decrementally for a graph
G undergoing edge deletions.
We set k = dlog ρe as in the pseudocode of Figure 2 and maintain k instances of the dynamic
version of Light-Spectral-Sparsify above. We maintain the k graphs G0 , . . . , Gk , B1 , . . . , Bk ,
and H1 , . . . , Hk as in the pseudocode. For every 1 ≤ i ≤ k we maintain Hi and Bi as the two
21

results of running the decremental version of Light-Spectral-Sparsify on Gi−1 and maintain
Gi as the graph Hi \ Bi . As argued above (for H 0 in Section 4.4.3), no edge is ever added to
Gi = Hi \ Bi for every 1 ≤ i ≤ k and we can thus use our purely decremental implementation of
Light-Spectral-Sparsify.
At the initialization, we additionally count the number of edges of every graph Gi and ignore
every graph Gi with less than (c + 1) ln n edges. Formally we set k maximal such that Gk has at
least (c + 1) ln n edges.
S
The output of our algorithm is the graph H = ki=1 Bi ∪ Gk . Now by the same arguments as for
the static case, H gives the same guarantees as in Lemmas 4.6 and 4.7. Thus, by our choices of
k and t, H is a (1 ± )-spectral sparsifier of size O(c−2 log3 ρ log4 n log W + mρ−1 ). As the total
running time is dominated by the running time of the k instances of the decremental algorithm for
Light-Spectral-Sparsify, the total update time is O(cm−2 log3 ρ log5 n). The guarantees of our
decremental sparsifier algorithm can be summarized as follows.
Lemma 4.16. For every 0 <  ≤ 1, every 1 ≤ ρ ≤ m, and every c ≥ 1, there is a decremental
algorithm for maintaining, with probability at least 1 − 1/nc against an oblivious adversary, a
(1 ± )-spectral sparsifier H of size O(c−2 log3 ρ log4 n log W + mρ−1 ) for an undirected graph G
with non-negative edge weights that has a total update time of O(cm−2 log3 ρ log5 n), where W is
the ratio between the largest and the smallest edge weight in G.

4.5

Turning Decremental Spectral Sparsifier into Fully Dynamic Spectral Sparsifier

We use a well-known reduction to turn our decremental algorithm into a fully dynamic algorithm.
Lemma 4.17. Given a decremental algorithm for maintaining a (1 ± )-spectral (cut) sparsifier
of size S(m, n, W ) for an undirected graph with total update time m · T (m, n, W ), there is a fully
dynamic algorithm for maintaining a (1 ± )-spectral (cut) sparsifier of size O(S(m, n, W ) log n)
with amortized update time O(T (m, n, W ) log n).
Together with Lemma 4.16 this immediately implies Theorem 4.1. A similar reduction has been
used by Baswana et al. [BKS12] to turn their decremental spanner algorithm into a fully dynamic
one. The only additional aspect we need is the lemma below on the decomposability of spectral
sparsifiers. We prove this property first and then give the reduction, which carries over almost
literally from [BKS12].
Lemma 4.18 (Decomposability). Let G = (V, E) be an undirected weighted graph, let E1 , . . . , Ek
be a partition of the set of edges E, and let, for every 1 ≤ i ≤ k, Hi be a (1 ± )-spectral sparsifier
S
of Gi = (V, Ei ). Then H = ki=1 Hi is a (1 ± )-spectral sparsifier of G.
Proof. Because Hi is a spectral sparsifier of Gi , for any vector x and i = 1, . . . , k we have
(1 − )xT LHi x ≤ xT LGi x ≤ (1 + )xT LHi x
Summing these k inequalities, we get that
(1 − )xT LH x ≤ xT LG x ≤ (1 + )xT LH x,
which by definition means that H is a (1 ± )-spectral sparsifier of H.
22

Proof of Lemma 4.17. Set k = dlog (n2 )e. For each 1 ≤ i ≤ k, we maintain a set Ei ⊆ E of edges
and an instance Ai of the decremental algorithm running on the graph Gi = (V, Ei ). We also keep
a binary counter C that counts the number of insertions modulo n2 with the least significant bit in
C being the right-most one.
A deletion of some edge e is carried out by simply deleting e from the set Ei it is contained in
and propagating the deletion to instance Ai of the decremental algorithm.
An insertion of some edge e is carried out as follows. Let j be the highest (i.e., left-most) bit that
gets flipped in the counter when increasing the number of insertions. Thus, in the updated counter
the j-th bit is 1 and all lower bits (i.e., bits to the right of j) are 0. We first add the edge e as well
S
as all edges in j−1
i=1 Ei to Ej . Then we set Ei = ∅ for all 1 ≤ i ≤ j − 1. Finally, we re-initialize the
instance Aj on the new graph Gj = (V, Ej ).
We know bound the total update time for each instance Ai of the decremental algorithm. First,
observe that the i-th bit of the binary counter is reset after every 2i edge insertions. A simple
induction then shows that at any time Ei ≤ 2i for all 1 ≤ i ≤ k. Now consider an arbitrary
sequence of updates of length `. The instance Ai is re-initialized after every 2i insertions. It will
therefore be re-initialized at most `/2i times. For every re-initialization we pay a total update
time of |Ei | · T (|Ei |, n, W ) ≤ 2i T (m, n, W ). For the entire sequence of ` updates, the total time
spent for instance Ai is therefore (`/2i ) · 2i T (m, n, W ) = ` · T (m, n, W ). Thus we spend total time
O(` · T (m, n, W ) log n) for the whole algorithm, which amounts to an amortized update time of
O(T (m, n, W ) log n).

5

Dynamic Cut Sparsifier

In this section we give an algorithm for maintaining a cut sparsifier under edge deletions and
insertions with polylogarithmic worst-case update time. The main result of this section is as follows.
Theorem 5.1. There exists a fully dynamic randomized algorithm with polylogarithmic update time
for maintaining a (1 ± )-cut sparsifier H of a graph G, with probability at least 1 − n−c for any
0 <  ≤ 1 and c ≥ 1. Specifically, the algorithm either has worst-case update time
O(c−2 log2 ρ log5 n log W )
or amortized update time
O(c−2 log2 ρ log3 n log W )
and the size of H is
O(cn−2 log2 ρ log n log W + mρ−1 ) ,
where 1 ≤ ρ ≤ m is a parameter of choice. Here, W is the ratio between the largest and the smallest
edge weight in G. The ratio between the largest and the smallest edge weight in H is at most O(nW ).
By running the algorithm with basically ρ = m we additionally get that H has low arboricity,
i.e., it can be partitioned into a polylogarithmic number of trees. We will algorithmically exploit
the low arboricity property in Sections 6 and 8.
Corollary 5.2. There exists a fully dynamic randomized algorithm with polylogarithmic update time
for maintaining a (1 ± )-cut sparsifier H of a graph G, with probability at least 1 − n−c for any 0 <
 ≤ 1 and c ≥ 1. Specifically, the algorithm either has worst-case update time O(c−2 log7 n log W )
or amortized update time O(c−2 log5 n log W ). The arboricity of H is k = O(c−2 log3 n log W ).
23

Here, W is the ratio between the largest and the smallest edge weight in G. The ratio between the
largest and the smallest edge weight in H is at most O(nW ). We can maintain a partition of H
into disjoint forests T1 , . . . , Tk such that every vertex keeps a list of its neighbors together with its
degree in each forest Ti . After every update in G at most one edge is added to and at most one edge
is removed from each forest Ti .
After giving an overview of our algorithm, we first explain our cut sparsification scheme in a
static setting and prove its properties. Subsequently, we show how we can dynamically maintain the
edges of such a sparsifier with both amortized and worst-case update times by making this scheme
dynamic.

5.1

Algorithm Overview

Our Framework. The algorithm is based on the observation that the spectral sparsification
scheme outlined above in Section 3.1. becomes a cut sparsification algorithm if we simply replace
spanners by maximum weight spanning trees (MSTs). This is inspired by sampling according to
edge connectivities; the role of the MSTs is to certify lower bounds on the edge connectivities. We
observe that the framework does not require us to use exact MSTs. For our t-bundles we can use a
relaxed, approximate concept that we call α-MST that. Roughly speaking, an α-MST guarantees a
‘stretch’ of α in the infinity norm and, as long as it is sparse, does not necessarily have to be a tree.
Similarly to before, we define a t-bundle α-MST B as the union of a sequence of α-MSTs T1 , . . . Tt
where the edges of each tree are removed from the graph before computing the next α-MST. The
role of α-MST is to certify uniform lower bounds on the connectivity of edges; these bounds are
sufficiently large to allow uniform sampling with a fixed probability.
This process of peeling and sampling is repeated sufficiently often and our cut sparsifier then
is the union of all the t-bundle α-MSTs and the non-bundle edges remaining after taking out the
last bundle. Thus, the cut sparsifier consists of a polylogarithmic number of α-MSTs and a few
(polylogarithmic) additional edges. This means that for α-MSTs based on spanning trees, our cut
sparsifiers are not only sparse, but also have polylogarithmic arboricity, which is the minimum
number of forests into which a graph can be partitioned.
Simple Fully Dynamic Algorithm. Our approach immediately yields a fully dynamic algorithm
by using a fully dynamic algorithm for maintaining a spanning forest. Here we basically have
two choices. Either we use the randomized algorithm of Kapron, King, and Mountjoy [KKM13]
with polylogarithmic worst-case update time. Or we use the deterministic algorithm of Holm, de
Lichtenberg, and Thorup [HLT01] with polylogarithmic amortized update time. The latter algorithm
is slightly faster, at the cost of providing only amortized update-time guarantees. A t-bundle 2-MST
can be maintained fully dynamically by running, for each of the log W weight classes of the graph, t
instances of the dynamic spanning tree algorithm in a ‘chain’.
An important observation about the spanning forest algorithm is that with every update in the
graph, at most one edge is changed in the spanning forest: If for example an edge is deleted from
the spanning forest, it is replaced by another edge, but no other changes are added to the tree.
S
Therefore a single update in G can only cause one update for each graph Gi = G \ i−1
j=1 Tj and
Ti . This means that each instance of the spanning forest algorithm creates at most one ‘artificial’
update that the next instance has to deal with. In this way, each dynamic spanning forest instance
used for the t-bundle has polylogarithmic update time. As t = poly(log n), the update time for
maintaining a t-bundle is also polylogarithmic. The remaining steps of the algorithm can be
24

carried out dynamically in the straightforward way and overall give us polylogarithmic worst-case
or amortized update time.
A technical detail of our algorithm is that the high-probability correctness achieved by the
Chernoff bounds only holds for a polynomial number of updates in the graph. We thus have to
restart the algorithm periodically. This is trivial when we are shooting for an amortized update time.
For a worst-case guarantee we can neither completely restart the algorithm nor change all edges of
the sparsifier in one time step. We therefore keep two instances of our algorithm that maintain two
sparsifiers of two alternately growing and shrinking subgraphs that at any time partition the graph.
This allows us to take a blend of these two subgraph sparsifiers as our end result and take turns in
periodically restarting the two instances of the algorithm.

5.2

Definitions

We will work with a relaxed notion of an MST, which will be useful when maintaining an exact
maximum spanning tree is hard (as is the case for worst-case update time guarantees).
Definition 5.3. A subgraph T of an undirected graph G is an α-MST (α ≥ 1) if for every edge
e = (u, v) of G there is a path π from u to v such that wG (e) ≤ αwG (f ) for every edge f on π.
Note that in this definition we do not demand that T is a tree; any subgraph with these properties
will be fine. A maximum spanning tree in this terminology is a 1-MST.
Definition 5.4. A t-bundle α-MST (t, α ≥ 1) of an undirected graph G is the union B = ki=1 Ti
S
of a sequence of graphs T1 , . . . , Tt such that, for every 1 ≤ i ≤ t, Ti is an α-MST of G \ i−1
j=1 Tj .
S

We can imagine such a t-bundle being obtained by iteratively peeling-off α-MSTs from G.

5.3

A Simple Cut Sparsification Algorithm

We begin with algorithm Light-Cut-Sparsify in Figure 3; this is the core iteration used to
compute a sparser cut approximation with approximately half the edges. Algorithm Cut-Sparsify
in Figure 3 is the full sparsification routine.
The properties of these algorithm are given in the following lemmas.
Lemma 5.5. The output H of algorithm Light-Cut-Sparsify is a (1 ± )-cut approximation of
the input G, with probability 1 − n−c .
We will need a slight generalization of a Theorem in [FHH+ 11].
Lemma 5.6. (generalization of Theorem 1.1 [FHH+ 11]) Let H be obtained from a graph G with
weights in (1/2, 1] by independently sampling edge edge e with probability pe ≥ ρ/λG (e), where
ρ = Cξ c log2 n/42 , and λG (e) is the local edge connectivity of edge e, Cξ is an explicitly known
constant. Then H is a (1 ± )-cut sparsifier, with probability at least 1 − n−c .
Proof. (Sketch) The generalization lies in introducing the parameter c to control the probability of
failure. This reflects the standard behavior of Chernoff bounds: increasing the number of samples
by a factor of c drives down the failure probability by a factor of n−c . Also, the original theorem
assumes that all edges are unweighted, but a standard variant of the Chernoff bound can absorb
constant ranges, with a corresponding constant factor increase in the number of samples. Finally,
the original theorem is stated with pe = ρ/λG (e), but all arguments remain identical if this is relaxed
to an inequality.
25

Light-Cut-Sparsify (G, c, )
1. t ← Cξ cα log W log2 n/2
2. Let B be a t-bundle α-MST of G
3. H := B
4. For each edge e ∈ G \ B
(a) With probability 1/4 add e to H with 4wH (e) ← wG (e)
5. Return (H, B)

Figure 3: Light-Cut-Sparsify (G, c, ). We give a dynamic implementation of this algorithm
in Section 5.4.2. In particular we dynamically maintain the t-bundle α-MST B which results in a
dynamically changing graph G \ B.

Cut-Sparsify (G, c, )
1. k ← dlog ρe
2. G0 ← G
3. B0 ← (V, ∅)
4. for i = 1 to k
(a) (Hi , Bi ) ← Light-Cut-Sparsify(G, c + 1, /(2k))
(b) Gi+1 ← Hi \ Bi
(c) if Gi+1 has less than (c + 2) ln n edges then break
5. H ←

S

1≤j≤i Bj

(* break loop *)

∪ Gi+1

6. return (H, {Bj }ij=1 , Gi+1 )

Figure 4: Cut-Sparsify (G, c, ) We give a dynamic implementation of this algorithm in Section 5.4.3. In particular we dynamically maintain each Hi and Bi as the result of a dynamic
implementation of Light-Cut-Sparsify which results in dynamically changing graphs Gi .

26

Proof. Suppose without loss of generality that the maximum weight in G is 1. We decompose G
into log W edge-disjoint graphs, where Gi consists of the edges with weights in (2−(i+1) , 2−i ] plus
Bi = B/2−(i+1) , where B is the bundle returned by the algorithm.
By definition of the α-MST t-bundle, the connectivity of each edge of Gi \ Bi in Gi is at least
4ρc, for c = d log W where ρ is as defined in Lemma 5.6. Assume for a moment that all edges in Bi
are also in (2−(i+1) , 2−i ]. Then we can set pe = 1 for each e ∈ Bi and pe = 1/4 for all other edges,
and apply Lemma 5.6. In this way we get that Hi is (1 ± )-cut sparsifier with probability at least
1 − nd log W .
The assumption about Bi can be removed as follows. We observe that one can find a subgraph
0
Bi of Bi (by splitting weights when needed, and dropping smaller weights), such that Bi0 is a
t-bundle α-MST of Gi . This follows by the definition of the t-bundle α-MST . We can thus apply
the lemma on G0i = (Gi \ Bi ) ∪ Bi0 , and get that the sampled graph Hi0 is a (1 ± )-cut sparsifier.
We then observe that Gi = G0i ∪ (Bi \ Bi0 ) and Hi = G0i ∪ (Bi \ Bi0 ), from which it follows that Hi is
a (1 ± )-cut sparsifier of Gi .
Note: The number of logarithms in Light-Cut-Sparsify is not optimal. One can argue that
the lower bounds we compute can be used in place of the strong connectivities used in [BK15] and
reduce by one the number of logarithms. It is also possible to replace log W with log n by carefully
re-working some of the details in [BK15].
We finally have the following Lemmas. The proofs are identical to those for the corresponding
Lemmas in Section 4, so we omit them.
Lemma 5.7. The output H of algorithm Cut-Sparsify is a (1 ± )-spectral sparsifier of the input
G, with probability at least 1 − 1/nc+1 .
Lemma 5.8. With probability at least 1 − 2n−c , the number of iterations before algorithm CutSparsify terminates is
min{dlog ρe, dlog m/((c + 1) log n)e}.
Moreover the size of H is


O


X

|Bi | + m/ρ + c log n ,

1≤j≤i

and the size of the third output of the graph is at most max{O(c log n), O(m/ρ)}.

5.4

Dynamic Cut Sparsifier

We now explain how to implement the cut sparsifier algorithm of Section 5.3 dynamically. The
main building block of our algorithm is a fully dynamic algorithm for maintaining a spanning forest
with polylogarithmic update time. We either use an algorithm with worst-case update time, or
a slightly faster algorithm with amortized update time. In both algorithms, an insertion might
join two subtrees of the forest and after a deletion the forest is repaired by trying to find a single
replacement edge. This strongly bounds the number of changes in the forest after each update.
Theorem 5.9 ([KKM13, GKK+ 15]). There is a fully dynamic deterministic algorithm for maintaining a spanning forest T of an undirected graph G with worst-case update time O(log4 n). Every
time an edge e is inserted into G, the only potential change to T is the insertion of e. Every time
an edge e is deleted from G, the only potential change to T is the removal of e and possibly the
addition of at most one other edge to T . The algorithm is correct with high probability against an
oblivious adversary.
27

Theorem 5.10 ([HLT01]). There is a fully dynamic deterministic algorithm for maintaining a
minimum spanning forest T of a weighted undirected graph G with amortized update time O(log2 n).
Every time an edge e is inserted into G, the only potential change to T is the insertion of e. Every
time an edge e is deleted from G, the only potential change to T is the removal of e and possibly the
addition of at most one other edge to T .
We first explain how to use these algorithms in a straightforward way to maintain a 2-MST.
Subsequently we show how to dynamically implement the procedures Light-Cut-Sparsify and
Cut-Sparsify. The overall algorithm will use multiple instances of a dynamic spanning forest
algorithm, where outputs of one instance will be used as the input of the next instance. We will do
so in a strictly hierarchical manner which means that we can order the instances in a way such that
the output of instance i only affects instances i + 1 and above. In this way it is guaranteed that
the updates made to instance i are independent of the internal random choices of instance i, which
means that each instance i is running in the oblivious-adversary setting required for Theorem 5.9.
5.4.1

Dynamic Maintenance of 2-MST

For every 0 ≤ i ≤ blog W c, let Ei be the set of edges of weight between 2i and 2i+1 , i.e., Ei = {e ∈
E | 2i ≤ wG (e) < 2i+1 }, and run a separate instance of the dynamic spanning forest algorithm
for the edges in Ei . For every 0 ≤ i ≤ blog W c, let Fi be the spanning forest of the edges in Ei
maintained by the i-th instance. We claim that the union of all these trees is a 2-MST of G.
Lemma 5.11. T =

Sblog W c
i=0

Fi is a 2-MST of G.

Proof. Consider some edge e = (u, v) of G and let i be the (unique) index such that 2i ≤ wG (e) < 2i+1 .
Since Fi is spanning tree of G, there is a path π from u to v in Fi (and thus also in T ). Every edge
f of π is in the same weight class as e, i.e., 2i ≤ wG (f ) < 2i+1 . Thus, wG (e) < 2i+1 ≤ 2wG (f ) as
desired.
Every time an edge e is inserted or deleted, we determine the weight class i of e and perform
the update in the i-th instance of the spanning forest algorithm. This 2-MST of size O(n log W )
can thus be maintained with the same asymptotic update time as the dynamic spanning forest
algorithm.
We now show how to maintain a t-bundle 2-MST and consequently a (1 ± )-cut sparsifier H
S
according to the construction presented in Section 5.3. For the t-bundle 2-MST B = 1≤i≤k Ti we
S
Si−1
maintain, for every 1 ≤ i ≤ t, a 2-MST of G \ i−1
j=1 Tj . We now analyze how changes to G \ j=1 Tj
S
affect G \ ij=1 Tj (for every 1 ≤ i ≤ k):
• Whenever an edge e is inserted into G \
not.
– If e is added to Ti , then G \

Si

Si−1

j=1 Tj ,

j=1 Tj

the 2-MST algorithm either adds e to Ti or

does not change.

– If e is not added to Ti , then e is added to G \
• Whenever an edge e is deleted from G \

Si−1

j=1 Tj ,

Si

j=1 Tj .

either e is contained in Ti or not.

– If e is contained in Ti , then e is removed from Ti and some other edge f is added to Ti .
S
This edge f is removed from G \ ij=1 Tj .4
4

The edge e will not be added to G \

Si
j=1

Tj because it is removed from both G \

28

Si−1
j=1

Tj and Ti .

– If e is not contained in Ti , then e is removed from G \

Si

j=1 Tj .

i
Thus, every change to G \ i−1
j=1 Tj results in at most one change to G \ j=1 Tj . Consequently, a
single update to G results to at most one update in each instance of the dynamic MST algorithm.
For every update in G we therefore incur an amortized update time of O(t log4 n). Thus, we can
summarize the guarantees for maintaining a t-bundle 2-MST as follows.

S

S

Corollary 5.12. There are fully dynamic algorithms for maintaining a t-bundle 2-MST B (where
t ≥ 1 is an integer) of size O(tn log W ) with worst-case update time O(t log4 n) or amortized update
time O(t log2 n), respectively. After every update in G, the graph G \ B changes by at most one
edge.
5.4.2

Dynamic Implementation of Light-Cut-Sparsify

For this algorithm we set t = (Cξ + 2)dα−2 log W log2 n. Note that this value is slightly larger
than the one proposed in Figure 3. For the sparsification proof in Section 5.3 we have to argue that
by our choice of t certain events happen with high probability. In the dynamic algorithm we need
ensure the correctness for a polynomial number of versions of the graph, one version for each update
made to the graph. We show in Section 5.5 that it is sufficient to be correct for up to 4n2 updates
to the graph, as then we can extend the algorithm to an arbitrarily long sequence of updates. By
making t slightly large than in the static proof of Section 5.3 all the desired events happen with
high probability for all 4n2 versions of the graph by a union bound.
The first ingredient of the algorithm is to dynamically maintain a t-bundle 2-MST B using the
algorithm of Corollary 5.12 above. We now explain how to maintain a graph H 0 – with the intention
that H 0 contains the sampled non-bundle edges of G \ B – as follows: After every update in G
we first propagate the update to the algorithm for maintaining the t-bundle 2-MST B, possibly
changing B to react to the update. We then check whether the update in G and the change in B
cause an update in the complement graph G \ B.
• Whenever an edge is inserted into G \ B, it is added to H 0 with probability 1/4 and weight
4wG (e).
• Whenever an edge e is deleted from G \ B, it is removed from H 0 .
We now simply maintain the graph H as the union of B and H 0 and make it the first output of our
algorithm; the second output is B.
By the update rules above (and the increased value of t to accommodate for the increased
number of events), this dynamic algorithm imitates the static algorithm of Figure 3 and for the
resulting graph H we get the same guarantees as in Lemma 5.5. The update time of our dynamic
version of Light-Spectral-Sparsify is O(t log4 n) worst-case and O(t log2 n) worst-case, as it is
dominated by the time for maintaining the t-bundle 2-MST B.
As an additional property we get that with every update in G at most one change is performed
to H 0 = H \ B. Furthermore, for all edges added to H 0 weights are always increased by the same
factor. Therefore the ratio between the largest and the smallest edge weight in H 0 will always be
bounded by W , which is the value of this quantity in G (before the first deletion).
5.4.3

Dynamic Implementation of Cut-Sparsify

We set k = dlog min(ρ, m/((c + 2) log n))e and maintain k instances of the dynamic version of
Light-Cut-Sparsify above, using the other parameters just like in the pseudo-code of Figure 4.
29

By this choice of k we ensure that we do not have to check the breaking condition in the pseudo-code
explicitly, which is more suited for a dynamic setting where the number of edges in the maintained
subgraphs might grow and shrink.
We maintain the k graphs G0 , . . . , Gk , B1 , . . . , Bk , and H1 , . . . , Hk as in the pseudocode. For
every 1 ≤ i ≤ k we maintain Hi and Bi as the two results of running the dynamic version of
Light-Cut-Sparsify on Gi−1 and maintain Gi as the graph Hi \ Bi .
S
The output of our algorithm is the graph H = ki=1 Bi ∪ Gk . Note that, by our choice of k, Gk
has at most max(m/ρ, (c + 2) log n) edges. Now by the same arguments as for the static case, H
gives the same guarantees as in Lemmas 5.7 and 5.8 for up to a polynomial number of updates (here
at most 4n2 ) in the graph.
As argued above (for H 0 in Section 5.4.2), every update in Gi−1 results in at most one change
to Gi = Hi \ Bi for every 1 ≤ i ≤ k. By an inductive argument this means that every update
in G results in at most one change to Gi for every 1 ≤ i ≤ k. As each instance of the dynamic
Light-Cut-Sparsify algorithm has update time O(t log4 n) worst-case or O(t log2 n) amortized,
this implies that our overall algorithm has update time O(kt log4 n) or O(kt log2 n), respectively.
Together with Lemma 5.14 in Section 5.3, we have proved Theorem 5.1 stated at the beginning of
this section.
In Corollary 5.2 we additionally claim that for ρ = m we obtain a sparsifier with polylogarithmic
arboricity. This is true because the cut sparsifier H mainly consists of a collection of bundles, which
in turn consists of a collection of trees. In total, H consists of O(tk log W ) trees and O(c log n)
remaining edges in Gk , each of which can be seen as a separate tree. Furthermore we can maintain
the collection of trees explicitly with appropriate data structures for storing them.

5.5

Handling Arbitrarily Long Sequences of Updates

The high-probability guarantees of the algorithm above only holds for a polynomially bounded
number of updates. We now show how to extend it to an arbitrarily long sequence of updates
providing the same asymptotic update time and size of the sparsifier. We do this by concurrently
running two instances of the dynamic algorithm that periodically take turns in being restarted,
which is a fairly standard approach for such situations. The only new aspect necessary for our
purposes is that both instances explicitly maintain a sparsifier and when taking turns we cannot
simply replace all the edges of one sparsifier with the edges of the other sparsifier as processing
all these edges would violate the worst-case update time guarantee. For this reason we exploit
the decomposability of graph sparsifiers and maintain a ‘blend’ of the two sparsifiers computed by
the concurrent instances of the dynamic algorithm. This step is not necessary for other dynamic
problems such as connectivity where we only have to make sure that the query is delegated to the
currently active instance.
Lemma 5.13 (Decomposability). Let G = (V, E) be an undirected weighted graph, let E1 , . . . , Ek
be a partition of the set of edges E, and let, for every 1 ≤ i ≤ k, Hi be a (1 ± )-cut sparsifier of
S
Gi = (V, Ei ). Then H = ki=1 Hi is a (1 ± )-cut sparsifier of G.
Proof. Let U be a cut in G. First observe that
wG (∂G (U )) = wG (

k
[

i=1

∂Gi (U )) =

k
X
i=1

30

wG (∂Gi (U )) =

k
X
i=1

wGi (∂Gi (U ))

and similarly wH (∂H (U )) =

Pk

i=1 wHi (∂Hi (U )).

Now since

(1 − )wHi (∂Hi (U )) ≤ wGi (∂Gi (U )) ≤ (1 + )wHi (∂Hi (U ))
for every 1 ≤ i ≤ k, we have
(1 − )wH (∂H (U )) = (1 − )

k
X
i=1

wHi (∂Hi (U )) ≤

k
X

wGi (∂Gi (U )) = wG (∂G (U ))

i=1

= · · · ≤ (1 + )wH (∂H (U )) .

Lemma 5.14. Assume there is a fully dynamic algorithm for maintaining a (1 ± )-cut (spectral)
sparsifier of size at most S(m, n, W ) with worst-case update time T (m, n, W ) for up to 4n2 updates
in G. Then there also is a fully dynamic algorithm for maintaining a (1 ± )-cut (spectral) sparsifier
of size at most O(S(m, n, W )) with worst-case update time O(T (m, n, W )) for an arbitrary number
of updates.
Proof. We exploit the decomposability of cut sparsifiers. We maintain a partition of G into two
disjoint subgraphs G1 and G2 and run two instances A1 and A2 of the dynamic algorithm on
G1 and G2 , respectively. These two algorithms maintain a (1 ± )-sparsifier of H1 of G1 and a
(1 ± )-sparsifier H2 of G2 . By the decomposability stated in Lemmas 5.13 and 4.18, the union
H := H1 ∪ H2 is a (1 ± )-sparsifier of G = G1 ∪ G2 .
We divide the sequence of updates into phases of length n2 each. In each phase of updates one
of the two instances A1 , A2 is in the state growing and the other one is in the state shrinking. A1
and A2 switch their states at the end of each phase. In the following we describe the algorithm’s
actions during one phase. Assume without loss of generality that, in the phase we are fixing, A1 is
growing and A2 is shrinking.
At the beginning of the phase we restart the growing instance A1 . We will orchestrate the
algorithm in such a way that at the beginning of the phase G1 is the empty graph and G2 = G.
After every update in G we execute the following steps:
1. If the update was the insertion of some edge e, then e is added to the graph G1 and this
insertion is propagated to the growing instance A1 .
2. If the update was the deletion of some edge e, then e is removed from the graph Gi it is
contained in and this deletion is propagated to the corresponding instance Ai .
3. In addition to processing the update in G, if G2 is non-empty, then one arbitrary edge e is
first removed from G2 and deleted from instance A2 and then added to G1 and inserted into
instance A1 .
Observe that these rules indeed guarantee that G1 and G2 are disjoint and together contain all
edges of G. Furthermore, since the graph G2 of the shrinking instance has at most n2 edges at the
beginning of the phase, the length of n2 updates per phase guarantees that G2 is empty at the end
of the phase. Thus, the growing instance always starts with an empty graph G1 .
As both H1 and H2 have size at most S(n, m, W ), the size of H = H1 ∪ H2 is O(S(n, m, W )).
With every update in G we perform at most 2 updates in each of A1 and A2 . It follows that the
worst-case update time of our overall algorithm is O(T (m, n, W )). Furthermore since each of the
instances A1 and A2 is restarted every other phase, each instance of the dynamic algorithm sees at
most 4n2 updates before it is restarted.
31

6

Application of Dynamic Cut Sparsifier: Undirected Bipartite
Min-Cut

We now utilize our sparsifier data structure to maintain a (2+)-approximate st-min-cut in amortized
O(poly(log n, −1 )) time per update. In this section, we will define several tools that are crucial for
the better analyses in Sections 7 and 8.
This result is a weaker form of Theorem 1.3 with an approximation factor of 2 +  instead of
1 + . The main result that we will show in this section is:
Theorem 6.1. For every 0 <  ≤ 1, there is a fully dynamic algorithm for maintaining a (2 + )approximate minimum cut in an unweighted undirected graph that’s a bipartite graph with source/sink
s and t attached to each of the partitions with amortized update time O(poly(log n, −1 )).
To add motivation for solving this problem, we would like to point out that there are examples
in which the maximum s − t flow is much larger than the minimum vertex cover, and we cannot
simply consider the problem as finding a maximum matching in GA,B . Specifically, let A = Ak2 ∪ Ak
and B = Bk2 ∪ Bk , where |Ak |, |Bk | = k and |Ak2 |, |Bk2 | = k 2 , then construct a complete bipartite
graph on (Ak2 , Bk ), (Ak , Bk ), (Ak , Bk2 ), while having no edges between Ak2 and Bk2 . A vertex cover
would be Ak ∪ Bk ∪ {s, t}, but we can achieve a max-flow in G of Ω(k 2 ).
Accordingly, the objective cannot be approximated using matching routines even in the static case.
However, the solution can still be approximated using recent developments in flow algorithms [She13,
KLO+ 14, Pen16]. Below we will show that these routines can be sped up on dynamic graphs
using multiple layers of sparsification. Specifically, the cut sparsifiers from Section 5.4 allow us to
dynamically maintain a (1 + )-approximation of the solution value, as well as some form of query
access to the minimum cut, in O(poly(log n, −1 )) per update.
The section is organized as follows. Section 6.1 will give some of the high level ideas and
critical observations on which our dynamic algorithm will hinge. Section 6.2 will present the
dynamic algorithm for maintaining a (2 + )-approximate minimum s − t cut, prove that the
approximation factor is correct, and show that the dynamic update time is O(poly(log n, −1 )) if
we can dynamically update all data structures necessary for the algorithm in O(poly(log n, −1 ))
time. Finally, Section 6.3 will present all of the necessary data structures and show how we can
dynamically maintain them in O(poly(log n, −1 )) time.

6.1

Key Observations and Definitions

Our starting point is the observation that a small solution value implies a small vertex cover.
Lemma 3.1. The minimum vertex cover in G has size at most OP T + 2 where OP T is the size of
the minimum s − t cut in G.
Proof. Denote the minimum vertex cover as MVC, and the minimum s − t cut in G as (S, S̄) where
S = {s} ∪ As ∪ Bs and S̄ = {t} ∪ At ∪ Bt . Hence, we must have OP T ≥ |At | + |Bs | + |E(As , Bt )|
where E(As , Bt ) are all of the edges between As and Bt .
Let VA (As , Bt ) denote all of the vertices in A that are incident to an edge in E(As , Bt ), so
|VA (As , Bt )| ≤ |E(As , Bt )|. We know GA,B is bipartite, so At ∪ Bs ∪ VA (As , Bt ) must be a vertex
cover in GA,B , which implies |MVC| ≤ OP T + 2 by adding s and t to the cover.

32

Our goal, for the rest of this section, is to show ways of reducing the graph onto a small vertex
cover, while preserving the flow value. The first issue that we encounter is that the minimum vertex
cover can also change during the updates. However, in our case, the low arboricity property of the
sparsifier given in Corollary 5.2 gives a more direct way of obtaining a small cover:
Lemma 6.2. For any tree T , the vertex cover of all vertices other than the leaves is within a
2-approximation of the minimum vertex cover.
This is proven in Appendix B. We suspect that this is a folklore result, but it was difficult to
find a citation of it, as there exist far better algorithms for maintaining vertex covers on dynamic
trees [GS09]. Since there are at most O(poly(log n, −1 )) trees, and the overall vertex cover needs to
be at least the size of any cover in one of the trees, we can set the cover as the set of all non-leaf
vertices in the trees.
Definition 6.3. Given a set of disjoint spanning forests F = F1 ∪· . . . ∪· FK , we say that VC =
i∈[K] VCi is a branch vertex cover of F , if each VCi is the set of all vertices other than the
leaves in Fi
S

Corollary 6.4. For any graph G = (V, E) and corresponding sparsified graph G̃ = F1 ∪· . . . ∪· FK . If
VC is a branch vertex cover of G̃, then, VC is a 2K-approximate vertex cover of G̃. Furthermore,
any x ∈ V \ VC has degree at most K in G̃
Proof. Since the size of a minimum vertex cover in subgraph can only be smaller, we have
|MVCFi | ≤ |MVCG |.
Coupling this the choice of |VC| gives |VCi | ≤ 2|MVCFi |, and summing over all K trees gives the
bound. The bound on the degree of x follows from all leaves having degree 1.
We will ensure that s and t are placed in the cover, and use X to denote the non-cover vertices.
If we let the neighborhood of x be N (x), its interaction with various partitions of S can be described
as:
Definition 6.5. For a cut on VC, S ⊆ VC, and a non-cover vertex x ∈ X with neighborhood N (x),
let
1. w(x, S) :=

P

u∈S∩N (x) w(x, u),

2. w(x) (S) := min{w(x, S), w(x, VC \ S)}.
Definition 6.6. Given a graph G = (V, E) and some Vb ⊆ V such that Vb is a vertex cover of G,
and X = V \ Vb
1. For any S ⊂ V , let ∆G (S) be the weight of cut S on G
2. For any SVb ⊂ Vb , let the weight of a cut that is minimally extended from SVb then be given by
∆G (SVb ) := ∆G\X (SVb ) +

X
x∈X

w(x) (SVb ),

Definition 6.7. Given G = (VG , EG ) and H = (VH , EH ) such that VH ⊆ VG and Vb is a vertex
cover of both graphs
33

1. If VH = VG , then we say H ≈ G if for any S ⊂ VG
(1 − )∆H (S) ≤ ∆G (S) ≤ (1 + )∆H (S)
2. If VH ⊂ VG , then we say H ≈Vb G, if for any SVb ⊂ Vb
(1 − )∆H (SVb ) ≤ ∆G (SVb ) ≤ (1 + )∆H (SVb )
Note that if some x ∈ X has degree 1, it will always belong to the same side as its neighbor
in a minimum s − t cut; while if x is incident to two neighbors u and v, it will always go with the
neighbor with smaller weight. That means that if w(x, u) ≤ w(x, v), then this is equivalent to an
edge of weight w(x, u) between u and v. This suggests that we can reduce the star out of x, Nx , to
a set of edges on its neighborhood. We formalize the construction of this graph, Kx , as well as the
resulting graph by removing all of X below:
Definition 6.8. Given a weighted graph G = (V, E) and w(u, v) → R+ , and any S, let: Kx be the
clique generated by running VertexElimination: for any two neighbors u and v of x, the edge
weight of (u, v)x is
w(x, v)w(x, u)
P
.
i∈N (x) w(x, i)
For some vertex cover VC and independent set X = V \ VC, we let GVC = (G \ X) ∪

S

x∈X

Kx

Note that we’re using a subscript x to denote the origin of the edge. Specifically, an edge
ex ∈ GVC implies that ex ∈ Kx , and an edge e∅ ∈ GVC means it’s from VC, i.e. e∅ ∈ G \ X. Note
that GVC also defines a weight for each cut SVC ⊂ VC, where ∆GVC (SVC ). The crucial property of
Definition 6.8 is that it preserves the values all cuts within a factor of 2. We prove the following in
Appendix B.
Theorem 6.9. Given a weighted graph G = (V, E) and w(u, v) → R+ , with some vertex cover VC
and independent set X = V \ VC. For any SV C ⊂ VC
1
∆G (SV C ) ≤ ∆GVC (SV C ) ≤ ∆G (SV C )
2
Lemma 6.10. Given G = (V, E) with all weights in [γ, γU ], along with vertex cover VC and
independent set X, such that any x ∈ X has degree at most d. Then the weight of any edge in GVC
is in [γ(dU )−1 , γU ]

6.2

Dynamic Algorithm for Maintaining a Minimum s − t Cut on Bipartite
Graphs

Our algorithm can then be viewed as dynamically maintaining this cover using two layers of dynamic
graph sparsifiers intermixed with elimination routines. Its main steps are shown in Figure 5.
One issue with maintaining a cut is that its two sides could have size O(n), which cannot be
returned in amortized O(poly(log n, −1 )) time. Instead, we will maintain the cut SbVC ⊂ VC with
s ∈ SbVC , and allow querying of any vertex. For a vertex v ∈ VC, return v is with s iff v ∈ SbVC ,
which takes O(1) time. For a vertex x ∈
/ VC, return that x is with s iff w(x, SbVC ) = w(x) (SbVC ) in

34

1. Dynamically maintain a sparsified G, which we will denote G̃
2. Dynamically maintain a branch vertex cover, VC, of G̃, where we ensure s, t ∈ VC
3. Dynamically maintain multi-graph G̃VC
4. Dynamically maintain a sparsified G̃VC , which we will denote as H with vertex set V
5. Every 2 ∆H (SbVC ) dynamic steps, recompute SbVC ⊂ VC, an approximate minimum s − t
cut on H, ignoring all degree zero vertices

Figure 5: Dynamic (2 + )-approximate Minimum s − t Cut
G̃, taking O(poly(log n, −1 )) time to compute w(x, SbVC ) and w(x, VC \ SbVC ). Specifically, the cut
will be
Sb = SbV C ∪ {x ∈ V \ VC : w(x, SbV C ) = w(x) (SbV C )},
the extension of SbVC on G̃ which allows for the O(poly(log n, −1 )) query computation by Corollary 5.2
and Corollary 6.4.
We first establish the quality of this cut on H that we maintain:
Theorem 6.11. Computing a (1 + b)-approximate minimum s − t cut in H as in Step 5 of Figure 5

takes O(OP T · poly(log n, −1 )) time for b = O(1)
, and cut SbVC ⊂ VC can be extended to Sb a
2(1 + b)5 -approximate minimum s − t cut in G with high probability
Proof. G̃ = F1 ∪· . . . ∪· FK for some K = O(poly(log n, −1 )) by Corollary 5.2, so from Lemma 3.1 and
Corollary 6.4, we know |VC| = O(OP T · poly(log n, −1 )). From Corollary 5.2, the weights of G̃ are
in [1, O(n)], and Lemma 6.10 implies that the weights of G̃VC are in [O(n−1 poly(log n, −1 ))−1 , O(n)].
Further, each Kx of G̃VC has at most K 2 = O(poly(log n, −1 )) edges, so G̃VC has O(n·poly(log n, −1 ))
edges. Corollary 5.2 then tells us that H has O(|VC| · poly(log n, −1 )) = O(OP T · poly(log n, −1 ))
edges, and that we can find a (1 + b) approximate minimum s − t cut in H, SbV C in O(OP T ·
poly(log n, −1 )) time.
From Corollary 5.2, we assume that H ≈b G̃VC and G ≈b G̃ with high probability.
Suppose SbV C ⊂ VC is returned as a (1 + b)-approximate minimum s − t cut in H, and let
Sb = SbV C ∪ {x ∈ V \ VC : w(x, SbV C ) = w(x) (SbV C )}
be its extension onto G̃. The left-hand side of Theorem 6.9 implies
∆G̃ (SbV C ) ≤ 2∆G̃V C (SbV C ),
which along with the approximations G ≈b G̃ and G̃V C ≈b H gives
b ≤ (1 + b)∆ (S)
b ≤ 2(1 + b)∆
b
b)2 ∆H (SbV C ).
∆G (S)
G̃
G̃VC (SV C ) ≤ 2(1 + 

On the other hand, let S ⊂ V be the minimum s − t cut in G, and S V C ⊂ VC be its restriction
to VC. Since right-hand side of Theorem 6.9 is over optimum choices of V \ SV C , we have
∆G̃ (S) ≥ ∆G̃ (S V C ) ≥ ∆G̃V C (S V C ),
35

which when combined with the approximations G ≈b G̃ and G̃V C ≈b H gives
∆G (S) ≥ (1 − b)∆G̃ (S) ≥ (1 − b)∆G̃VC (S V C ) ≥ (1 − b)2 ∆H (S V C ).
The result then follows from the near-optimality of SbV C on H, ∆H (S V C ) ≥ (1 − b)∆H (SbV C ).
Corollary 6.12. The dynamic algorithm maintains a (2 + )-approximate minimum s − t cut in G,
and will only compute an approximate minimum s − t cut on H every O(OP T ) dynamic steps.

Proof. Choosing b = O(1)
in Theorem 6.11 can give a (2 + 2 )-approximate minimum s − t cut in
G. Borrowing notation from the proof of Theorem 6.11, an approximate minimum s − t cut on H
b ≤ 2(1 + b)2 ∆H (SbVC ), so
will be re-computed in 2 ∆H (SbVC ) dynamic steps. OP T = ∆G (S̄) ≤ ∆G (S)
∆H (SbVC ) = O(OP T )

6.3

Dynamically Updating Data Structures

As was shown in Corollary 6.12, the dynamic algorithm maintains a (2 + )-approximate minimum
s − t cut of G, an approximate minimum s − t cut of H is computed every O(OP T ), and that
computation takes O(OP T · poly(log n, −1 )) time from Theorem 6.11. Therefore, in order to
establish that the amortized dynamic update time is O(poly(log n, −1 )), it suffices to show that all
data structures can be maintained in O(poly(log n, −1 )) time per dynamic update, thereby finishing
the proof of Theorem 6.1. As a result of Corollary 5.2, it suffices to show the following
Theorem 6.13. For each addition/deletion of an edge in G̃, data structures for G̃, VC, G̃VC , and
H can be maintained in O(poly(log n, −1 )) time.
Bounds on the dynamic update time of each data structure will all ultimately follow from the
O(poly(log n, −1 )) degree bound for G̃ of all vertices not in the branch vertex cover, VC. This is a
direct result of the O(poly(log n, −1 )) arboricity of G̃ from Corollary 5.2, and the properties of a
branch vertex cover of G̃ in Corollary 6.4.
Data structure for G̃: A list of O(poly(log n, −1 )) spanning forests, which we will denote
SPANNERSG .
Data structure for adjacency lists of G̃:, We will denote it as ADJ-LISTG̃ , and it will have,
for each vertex v, two lists LEAFv and BRANCHv :
• The list LEAFv will have the adjacency list of v for each spanning forest in SPANNERSG
in which v is a leaf.
• Similarly, the list BRANCHv will have the adjacency list of v edge for each spanning forest
in SPANNERSG in which v is not a leaf.
Data structure for VC: We will denote it as VCG̃ , which will be a list of all vertices v whose list
BRANCHv is non-empty.

36

InsertVC(G, VC, v)
1. Delete all edges ev ∈ Kv in GRAPHVC .
2. For all edges e adjacent to v in ADJ-LISTG̃ , insert e∅ into GRAPHVC .
Figure 6: Moving a Vertex into VC

RemoveVC(G, VC, v)
1. For all edges e adjacent to v in ADJ-LISTG̃ , delete e∅ from GRAPHVC .
2. Use all incident edges to compute Kv and insert all ev ∈ Kv into GRAPHVC
Figure 7: Removing a Vertex from VC
Data structure for G̃VC : We will denote it as GRAPHVC , and it will contain an adjacency list,
ADJv , for each vertex v ∈ VC. Assume that each ADJv has a data structure such that deletion
and insertion of any edge takes O(log n) time.
Data structure for H: We will denote it as SPARSEVC , and it will be the sparsified multi-graph.
We first show that moving a vertex in / out of the vertex cover can be done in O(poly(log n, −1 ))
time, assuming that the degree of the vertex added/removed is small. Note that the small number
of forests in G̃ and the choice of VC allow us to meet this requirement.
Lemma 6.14. If v is not in VCG̃ , then running INSERTVC (v) on GRAPHVC , using ADJ-LISTG̃ ,
will output GRAPHVC equivalent to G̃VC∪v of ADJ-LISTG̃ in O(poly(log n, −1 )) time.
Proof. Costs of the two steps are:
1. Delete all edges ev ∈ Kv in GRAPHVC . This requires finding all incident vertices to v in
LEAFv and BRANCHv , which is at most O(poly(log n, −1 )) because BRANCHv is empty
due to v not in VCG̃ . Every pair of vertices has a corresponding edge ev in GRAPHVC , so
this takes O(poly(log n, −1 )) time.
2. There are at most O(poly(log n, −1 )) edges adjacent to v in ADJ-LISTG̃ , so adding all these
edges into GRAPHVC takes O(poly(log n, −1 )) time.
If v is not in VCG , then v must only be incident to VC in ADJ-LISTG̃ . Therefore in G̃VC∪v , v
will only be incident to edges e∅ for each e incident to v in ADJ-LISTG̃ , and no edges ev will be in
G̃VC∪v . INSERTVC (v) will perform exactly these operations on GRAPHVC .

37

UpdateADJ(G, VC, e)
1. If e has been added/deleted, then add/delete e from the adjacency list of u and v for Fi in
ADJ-LISTG̃ , which will be denoted Lu,i and Lv,i , respectively.
2. For u and v, if Lv,i has at most one adjacent vertex, place it in LEAFv , otherwise place it
in BRANCHv .
3. If the degree of u and v in Fi is zero before adding e, then place Lv,i in BRANCHv and
Lu,i in BRANCHu
4. For u and v, if degree of v is two before deleting e, check the other vertex incident to
v, say it is w, and if w has degree one in Fi then move Lv,i to BRANCHv and Lw,i to
BRANCHw .
5. For u and v, if degree of v is one before adding e, check the other vertex incident to v, say
it is w, and if w has degree one in Fi then move Lw,i to LEAFw .

Figure 8: Update ADJ-LISTG̃
Lemma 6.15. If BRANCHv is empty, then running REMOVEVC (v) on GRAPHVC , using
ADJ-LISTG̃ , will output GRAPHVC equivalent to G̃VC\v of ADJ-LISTG̃ in O(poly(log n, −1 ))
time.
Proof. Costs of the two steps are:
1. At most O(poly(log n, −1 )) edges are adjacent to v in ADJ-LISTG̃ , so deleting all these
edges from GRAPHVC takes O(poly(log n, −1 )) time.
2. v ∈
/ VC, so v has O(poly(log n, −1 )) neighbors, and using all incident edges to compute each
ev ∈ Kv and insert ev into GRAPHVC takes O(poly(log n, −1 )) time.
If BRANCHv is empty, then v must only be incident to VC in ADJ-LISTG̃ . Therefore in
G̃VC\v , v will never be incident to any edges e∅ , and for any of its neighbors w and z, (w, z)v will
be in ADJ-LISTG̃ . INSERTVC (v) will perform exactly these operations on GRAPHVC
We now consider updating ADJ-LISTG̃ given the addition/deletion of some edge. This process
is simple in terms of time complexity, but has a small wrinkle in maintaining the correct LEAF
and BRANCH structure. Specifically, for each forest, we can consider all of the degree one vertices
to be leaves, except for when there is a disjoint edge in the forest. Accordingly, steps 3, 4, and 5 of
the algorithm in Figure 8 will take care of this edge case.
Lemma 6.16. UpdateADJ(G, VC, e) takes O(log n) time and all vertices v such that Lv,i are in
BRANCHv , maintain a 2-approximate vertex cover of Fi .
Proof. Finding the adjacency list of u and v for Fi in ADJ-LISTG̃ takes O(log n) time. The rest of
the steps all take O(1) time, as they are just there to ensure we maintain the 2-approximate vertex
cover of Fi .
38

For all trees, other than a single edge, it suffices to put all vertices with degree ≥ 2 in the vertex
cover, and 2-approx tree theorem tells us that this is a 2-approximate vertex cover. Step 3 and 4
of Update ADJ-LISTG̃ ensure that in the single edge case, e = (u, v) that Lv,i is in BRANCHv
and Lu,i is in BRANCHu , which is still a 2-approximate vertex cover. Further, step 5 ensures that
anytime an edge is added to a tree that just contains a single edge, all vertices of degree one have
their adjacency list moved to the LEAF list.
6.3.1

Full Dynamic Update Process

Finally, we consider the addition/deletion of an edge in SPANNERSG . Specifically, let the edge
e = (u, v) be added/deleted from forest Fi . The above two operations allow us to reduce it to the
simpler case of both u and v being in VC. The update process will occur as follows:
1. For u and v, if v ∈
/ VCG̃ , then run InsertVC on GRAPHVC , VCG̃ , and v
2. Update ADJ-LISTG̃
3. If e was added/deleted from G̃, insert/delete edge e∅ from GRAPHVC and insert u and v into
VCG̃
4. For u and v, if BRANCHv is empty, then run RemoveVC on GRAPHVC , VCG̃ , and v, and
delete v from VCG̃
By Lemma 6.14, GRAPHVC is equivalent to G̃VC∪{u,v} on updated ADJ-LISTG̃ after step 3
because u and v are in VC. Similarly, the moving of u and v outside of VC ensures our final state is
good.
Proof of Theorem 6.13 : The full update process for ADJ-LISTG̃ , VCG̃ , and GRAPHVC
only calls InsertVC, RemoveVC, and UpdateADJ a constant number of times. Therefore, by
Lemma 6.14, Lemma 6.15, and Lemma 6.16 this process takes O(poly(log n, −1 )) time. This also
implies that at most O(poly(log n, −1 )) edges can be added/deleted from G̃V C , and by Corollary 5.2
maintaining H will take at most O(poly(log n, −1 )) time.

7

Vertex Sampling in Bipartite Graphs

We now design an improved method for reducing a graph onto one whose vertex size is O(|VC| poly(log n, −1 ))+
|X|/2. Instead of sampling edges of GVC , it samples vertices in X = V \ VC using GVC as a guide.
This question that we’re addressing, and the vertex sampling scheme, is identical to the terminal
cut sparsifier question addressed in [AGK14]. In the next section we will apply this sampling
scheme to obtain a vertex sparsification routine that will reduce onto a graph of size proportional to
O(|VC| poly(log n, −1 )) without losing a factor of 2 approximation.
We will reuse the notation from Section 6.1, and we encourage the reader to revisit the definitions
in that subsection. For this section, we will exclusively be dealing with subsets of VC, and we will
drop the VC subscript from each SVC . So, formally our goal is to find H so that for all S ⊂ VC,
(1 − )∆G (S) ≤ ∆H (S) ≤ (1 − )∆G (S).

39

This sampling scheme allows us to keep expectation of the cuts on VC to be exactly the same,
instead of having a factor 2 error from the conversion from G to GVC . The connection to GVC on
the other hand allows us to bound the variance of this sampling process as before.
In our application of this sampling routine to vertex sparsification, we will consider sparsifying
G \ X separately, so for simplicity, we assume here that (V C, X) is a bipartition and
[

G=

Nx

x∈X

Further, we first focus on the case where all vertices in X have degree d, and all edge weights in
X are within a factor of U from each other. We will show reductions from general cases to ones
meeting these assumptions in Subsection 8.1.1.
As before, let GVC be the multigraph generated by the clique edges from Theorem 6.9:
GVC =

[

Kx .

x∈X

Lemma 6.10 implies that the weights of every (multi) edge ex ∈ GVC are within a factor of O(U 2 d)
from each other.
As mentioned, we ultimately want to obtain a vertex sparsification scheme that reduces to size
O(|VC| poly(log n, −1 )) for further application. As a result, instead of doing a direct union bound
over all 2|VC| cuts to get a size of poly(|VC|) as in [AGK14], we need to invoke cut counting as with
cut sparsifier constructions. This necessitates the use of objects similar to t-bundles to identify
edges with small connectivity.
Our proof will use a similar structure to that of Fung et al. [FHH+ 11], particularly the cutcounting based analysis of cut sparsifiers. We will follow their definitions, which are in turn based
on the definition of edge strength by Benczur and Karger [BK15].
Definition 7.1. In a graph G, an edge is e k − heavy if the connectivity of its endpoints is at least
k in G. Furthermore, for a cut S, its k − projection is the set of k − heavy edges in the edges cut,
∂(S).
We will refer to edges that we cannot certify to be heavy as light. These edges are analogous to
the bundle edges from the cut sparsifier routine from Section 5.4.
Before we continue, we remark that these definitions of heavy/strong edges in [FHH+ 11, BK15]
is almost the opposite of definitions in spectral sparsification. In spectral sparsification, the edges
with high leverage scores are kept, and the low leverage score ones are sampled. This issue can
also be reflected in the robustness of this definition in the presence of weights: a natural way of
generalizing heaviness is to divide the connectivity of uv by the weight w(u, v). This leads to a
situation where halving the weight of an edge actually makes it heavier. In fact, these definitions
of heaviness / strength are measuring the connectivity in the graph between the endpoints of e,
instead of the strength of e itself. As our routines are in the cut-sparsification setting, we will use
these definitions in this version in order to be consistent with previous works [FHH+ 11, BK15], but
may switch to a different set of notations in a future edit.
The main result of [FHH+ 11], when restricted to graphs with bounded edge weights, states that
we can sample the O(log n−2 )-heavy edges by a factor of 2. Our goal is to prove the analogous
statement for sampling heavy vertices, which we define as follows:

40

Sample(G, VC, X heavy )
Input: Bipartite graph G with one bipartition VC, heavy subset X heavy of the other bipartition.
Output: Bipartite graph H with bipartition (VC, XH).
1. Initialize H ← ∅, XH = ∅.
2. For every x ∈ X heavy , flip fair coin with probability 1/2, if returns heads:
(a) H ← H + 2Nx .
(b) XH ← XH ∪ {x}
3. Return (H, XH).

Figure 9: Sampling Heavy Vertices
Definition 7.2. A subset of X, X heavy is a k-heavy subset if every pair of vertices u, v in some
Nx for some x ∈ X heavy is k-connected in the graph
Glight
/ heavy Kx .
VC = ∪x∈X
We will show in Section 8, these heavy/light subsets can be found by taking pre-images of more
restricted versions of t-bundles on GVC . Our main structural result is that a heavy subset can be
sampled uniformly while incurring -distortion.
Lemma 7.3. Given a bipartite graph G between VC and X such that X has maximum degree d
and all edge weights are in some range [γ, U γ], with U = O(poly(n)) and any non-negative γ. For
any , there is a parameter tmin = O(dU log n−2 ) such that if we’re given a subset X light of X so
that X heavy = X \ X light is γ(dU )t-heavy with t ≥ tmin then the graph consisting of the light vertices
and sampled heavy vertices,
H = N (X light ) ∪ Sample(G, VC, X heavy )
meets the condition:
|∆G (S) − ∆H (S)| ≤ ∆G (S)
for all subsets S ⊆ VC w.h.p. Here the constants in tmin depends on the failure probability in the
w.h.p.
The cut-counting proof of cut-sparsifiers from [FHH+ 11] essentially performs a union bound
over distinct sets of k-heavy projections over all cuts. We will perform the same here, but over
distinct partitions of Nx over all x in X heavy . We can first define the partition of a single vertex by
a cut S ⊆ VC as:
Nx (S) = {S ∩ N (x), N (x) \ S} .
Then we can define an equivalence relation on cuts as:
Definition 7.4. S1 ≡G S2 if for any x ∈ X heavy , Nx (S1 ) = Nx (S2 )

41

Note that this equivalence ignores the presence of edges in X light . So we need to further take
representatives of each equivalence class:
Definition 7.5. Define S rep to be the set of subsets S ⊂ VC such that
1. For every S ∈ S rep , there is some x ∈ X heavy s.t. Nx (S) 6= {Nx , ∅}, i.e. Nx is not entirely on
one side of the cut.
2. For any S1 , S2 ∈ S rep , S1 6≡G S2
3. For any S ⊂ VC such that S ∈
/ S rep , there exists S ∈ S rep such that
• S ≡G S, and
• ∆G (S) ≤ ∆G (S).
An immediate consequence of condition 1 is that for any S ∈ S rep we have ∆G (S) > γt(dU )−1 .
This set plays the same role as the unique k-projections in cut sparsifiers.
Lemma 7.6. Let H be obtained from G by sampling on X heavy , then for any element of S rep , S
we have:




|∆G (S) − ∆H (S)| > ∆G (S) = PH

h

Proof. Let Gsample = G \ x∈X light Nx and Hsample = H \
By construction of H, for any S ⊂ VC,

S

PH 

[

i

∆G (S) − ∆H (S) > ∆G (S) .

S,S≡G S

S

x∈X light

Nx be the graphs being sampled.

|∆G (S) − ∆H (S)| = ∆Gsample (S) − ∆Hsample (S) .
By construction of our equivalence relation, if S ≡G S,
∆Gsample (S) − ∆Hsample (S) = ∆Gsample (S) − ∆Hsample (S) .
due to them having the same part that’s not in H. Therefore, the failure probability is limited by
the element in the equivalence class with the smallest ∆G (S), i.e. S.
Corollary 7.7.
#

"

PH

[

"

|∆G (S) − ∆H (S)| > ∆G (S) = PH

#
[

|∆G (S) − ∆H (S)| > ∆G (S)

S∈S rep

S⊂VC

The key observation is that the sizes of subsets of S rep of certain sizes can be bounded using
cut-counting on GVC . For any S ⊂ VC, define
Kx (S) = EKx (S ∩ N (x), N (x) \ S),
which are the edges in Kx crossing S. Similar to S1 ≡G S2 , we can define S1 ≡GVC S2 if for any
x ∈ X heavy , Kx (S1 ) = Kx (S2 )
Lemma 7.8. For any S1 , S2 ⊆ VC, Nx (S1 ) = Nx (S2 ) iff Kx (S1 ) = Kx (S2 ). Therefore S1 , S2 ⊆ VC,
S1 ≡G S2 iff S1 ≡GVC S2 .
42

Proof. We construct Kx as a clique, so Kx (S1 ) = Kx (S2 ) iff S1 ∩ N (x) = S2 ∩ N (x) or S1 ∩ N (x) =
N (x) \ S2
Lemma 7.9. |{S ∈ S rep |∆GVC (S) ≤ K}| is less than or equal to the number of distinct γ(dU )−1 tprojections in cuts of weight at most K
Proof. Lemma 7.8 gives that S rep has the following properties for GVC
1. For every S ∈ S rep , there is some x ∈ X heavy s.t. Kx (S) 6= ∅.
2. For any S1 , S2 ∈ S rep , S1 6≡GVC S2
For any S ∈ S rep , let Eheavy (S) denote all the γ(dU )−1 t-heavy edges crossing S in GVC . The
property above gives:
[
Kx (S)
x∈X heavy

is a non-empty subset of Eheavy (S), and
[

Kx (S1 ) 6=

x∈X heavy

[

Kx (S2 )

∀S1 , S2 ∈ S rep .

x∈X heavy

Therefore, each S ∈ S rep such that ∆GVC (S) ≤ K, must be a distinct γ(dU )−1 t − projection of
weight at most K
It remains to combine this correspondence with cut counting to show the overall success
probability of the vertex sampling routine.
Proving this requires using Chernoff bounds. The bound that we will use is below, it can be
viewed as a scalar version of Theorem 1 of [Tro12].
Lemma 7.10. Let Y1 . . . Yn be random variables s.t.
1. 0 ≤ Yi ≤ 1.
2. µi = EYi [Yi ]
3. µ =

P

i µi

Then for any  ≥ 0
PY1 ...Yn

"
X
i

PY1 ...Yn

"
X
i

#

!

#

!

2 µ
Yi > (1 + )µ ≤ exp −
.
2
2 µ
Yi < (1 − )µ ≤ exp −
.
2

This bound can be invoked in our setting on a single cut S as follows:
Lemma 7.11. For each cut S, we have
!

2 ∆G (S)
PH [|∆H (S) − ∆G (S)| > ∆G (S)] ≤ 2 exp −
.
4γ
43

Proof. Let
wmax (S) = max{w(x) (S)}.
x∈X

We will only consider S ∈ S rep , so we know wmax (S) > 0, which implies wmax (S) ≥ γ. For each
S ⊆ S rep and for all x ∈ X, let Yx (S) be the random variable such that either
1. Yx (S) =

w(x) (S)
2wmax (S)

2. Yx (S) equals

if x ∈ X light

w(x) (S)
wmax (S)

w.p. 1/2, and 0 w.p. 1/2.
1
2wmax (S)

P

Accordingly, we have x∈X EYx (S) [Yx (S)] =
bound then follows from invoking Lemma 7.10.

P

x∈X

w(x) (S) =

1
2wmax (S) ∆G (S).

The

Proof. (Of Lemma 7.3)
Let ∆GVC (S) be the weight of cutting S ⊂ VC in GVC . From Theorem 6.9 for any S ∈ S rep that
∆G (S) ≥ ∆GVC (S). Therefore,
2 ∆G (S)
2 exp −
4γ
S⊆S rep

!

2 ∆GVC (S)
≤
2 exp −
4γ
S⊆S rep

!

X

X

The main cut-counting bound follows from Theorem 1.6 [FHH+ 11] on multi-graphs, and by our
construction of S rep gives:
(

|{S ∈ S

rep

|∆GVC (S) ≤ K}| ≤

−1

if K ≥ γ(dU )−1 t,
otherwise.

n2KdU (γt)
0

Each vertex adds weight at most γdU for any cut, so we can upper bound K by n2 γU because
d ≤ n. Invoking cut counting for intervals of length γ from K ≥ γ(dU )−1 t to K ≤ n2 γU allows us
to bound the overall failure probability by:

n2 U

≤

X
i=(dU )−1 t






X

S∈S rep
γi≤∆GVC (S)≤γ(i+1)

≤


!
2 ∆GVC (S) 

2 exp −


4γ

2U
n
X

i=(dU )−1 t

2n

2(i+1)dU t−1

2 i
exp −
4

!

=

2U
n
X

2

2n

 i
2(i+1)dU t−1 − 4 log
n

. (1)

i=(dU )−1 t

Note that we’re free to choose t, and it can be checked that for U ≤ nc1 , setting t ≥ (28 +
4c1 )c2 dU log n−2 bounds this by n−c2 for any c2 ≥ 1. Note that if U is larger than O(poly(n)),
we could set t = O(dU 2 log n−2 ) and still achieve w.h.p., but for our practical purposes assuming
U = O(poly(n)) is more than sufficient because U will always be O(poly(log n, −1 )).

44

8

Maintaining (1+)-Approximate Undirected Bipartite Min-Cut

In this section, we will again consider the bipartite minimum s − t cut problem of Section 6, and
will improve the approximation guarantee to (1 + ). This improvement will require many of the
techniques from Section 6, but we will bypass the loss of a factor 2 approximation by utilizing the
vertex sampling scheme presented in Section 7. A high level overview of these techniques is in
Section 3.3. The dynamic algorithm given in this section will rely heavily on the definitions and
observations of Subsection 6.1, which we encourage the reader to revisit.
Lemma 7.3, along with the framework from Section 6 allow us sample a large set of vertices
if the optimal minimum s − t cut is small, and will guarantee that the sampled vertices have
O(poly(log n, −1 )) degree. However, Lemma 7.3 as stated require incident edges of all sampled
vertices to have weight within factor O(poly(log n, −1 )) of one another. In this section, we integrate
this subroutine into the data structure framework, leading to our main result for approximating
undirected bipartite maximum flows:
Theorem 1.3. Given a dynamically changing unweighted, undirected, bipartite graph G = (A, B, E)
with demand −1 on every vertex in A and demand 1 on every vertex in B, we can maintain a
(1 − )-approximation to the value of the maximum flow, as well as query access to the associated
approximate minimum cut, with amortized update time poly(log n, −1 ) per edge insertion / deletion.
Section 8.1 will show how the vertex sampling scheme given in Section 7 can be iteratively
applied, reducing to a graph with O(|V C| poly(log n, −1 )) vertices and O(|V C| poly(log n, −1 ))
edges. This section will first present the full vertex sparsification scheme, and then examine the
two primary components of this scheme. Section 8.1.1 will show how we can pre-process a graph to
ensure that all edge weights of each sampled vertex are close to each other, which will be necessary
for bucketing sampled vertices. Section 8.1.2 will utilize these bounded properties and the vertex
sampling of Section 7 to give a vertex sparsification scheme for each bucket, culminating in a proof
of correctness for the full scheme in terms of approximation guarantees and bounds on the number of
edges and vertices. Section 8.1.3 will extend vertex sparsification to general graphs without bounds
on degree for the static case, proving Corollary 3.2.
Section 8.2 will then use this vertex sparsification scheme along with many of the components
from Section 6 to give a fully dynamic algorithm for maintaining a minimum s − t cut on a bipartite
graph. The correctness of this algorithm will follow from the correctness of the dynamic algorithm
in Section 6 and the correctness of vertex sparsification. Accordingly, it will then only be necessary
to establish that we can dynamically update all necessary data structures in O(poly(log n, −1 ))
time.

8.1

Vertex Sparsification in Quasi-Bipartite Graphs

The general framework of the routine is shown in Figure 10.
Theorem 8.1. Given any graph G, vertex cover VC and XG = V \ VC, such that the degree of
each vertex in XG is bounded by d, with weights in [γ, O(γW )] where log W = O(poly(log n)), and
error . Then there is a t = O(d2 log3 n−3 ) whereby VertexSparsify(G, VC, XG, d, ) returns H
s.t. w.h.p.
1. H \XG is a multi-graph on VC with O(|V C| poly(log n, −1 )) edges, and each Hi is a bipartition
with VC on one side, and at most O(|VC|t log n) vertices of XG on the other.
45

VertexSparsify(G, VC, XG, d, )
Input: Graph G with vertex cover VC and XG = V \ VC, such that the degree of each vertex
in XG is bounded by d.
b on the same vertex set as G s.t. G ≈
b
b
1. Build G
/2 G and for each x in X G, the weights are
within a factor of O(d/) of each other.
b by maximum edge weights in each Nx into G
b1 . . . G
b L , along with G
b \ XG
2. Bucket G

3. Set t = O(d2 log3 n−3 ), initialize H = (VC, ∅).
b \ XG and BoundedVertexSparsify each G
b i , giving Hi
4. With error /2, sparsify G

5. Return the union of each sparsified graph, H = H \ XG ∪· H1 ∪· . . . ∪· HL .

Figure 10: Vertex Sampling in G
2. H ≈VC
G.

3. All edge weights of H are in [γ, O(γnW )]
Here the constant in front of t depends on W as well as in the w.h.p. condition.
A proof of Theorem 8.1 will be given at the end of Section 8.1.2.
8.1.1

Reduction to Bounded Weight Case

The idea here will be to look at each Nx and move the low weight edges into G \ X , thereby ensuring
that the remaining edges in Nx have weight within a O(poly(log n, −1 )) factor. This will create a
multi-graph in G \ X, where will use the normal notation (u, v)x to denote an edge added by Nx .
Theorem 8.2. Given G with bipartition (V C, XG) with weights in [γ, γW ], such that the degree
of each vertex in XG is bounded by d, for any , VertexBucketing(G, V C, XG, d, ) will return
b=G
b\X ∪
b1 ∪
b L such that
G
· G
· . . . ∪· G
b
1. G ≈ G
b i , the weights of G
b i are in [γ, 2γd−1 ] for some γ
2. For each G
b must be in G
b\X
3. Any edge e∅ ∈ G
b i , then x has zero degree in G
b\G
b i , and the degree of x in
4. If x ∈ X has non-zero degree in G
b
Gi is bounded by d

Proof. Items 2, 3, and 4 follow from construction, and because XG is an independent set in G, we
b from Lemma 8.3 and Lemma 8.4 below.
can conclude that G ≈ G
Lemma 8.3. Consider a graph on three vertices, x, u, and v with edges between xu and xv. If
w(x, v) ≤ w(x, u), then the graph with edges xu with weight w(x, u) and uv with weight w(x, v) is
an -approximation on all cuts.
46

VertexBucketing(G, VC, XG, d, )
Input: Bipartite graph G with bipartition (VC, XG) s.t. the degree of each vertex in XG is
bounded by d.
b \ X = G \ X, and G
b i = (VC, ∅) for i = 1 . . . L with L = O(log W )
1. Initialize G

2. For each x ∈ XG
(a) Let (x, u) be the edge with maximum weight in Nx , where w(x, u) ∈ [γ2i−1 , γ2i ]
b \ X. Otherwise, put
(b) For each (x, v) ∈ Nx , if w(x, v) < d w(x, u), then put (u, v)x in G
bi
(x, v) in G
b \ X, and graphs G
b1 . . . G
bL
3. Return the multi-graph G

Figure 11: Vertex Bucketing in G
Proof. The only interesting cuts are singletons:
1. Removing v has w(x, v) before and after.
2. Removing x has w(x, u) + w(x, v) before, and w(x, u) after, a factor of  difference since
w(x, u) + w(x, v) ≤ (1 + )w(x, u).
3. Removing u has w(x, u) before, and w(x, u) + w(x, v) after, same as above.

Invoking this repeatedly on small stars gives:
Lemma 8.4. A star x with degree d can be reduced to one whose maximum and minimum weights
is within a factor of O(d−1 ) while only distorting cuts by a factor of 1 + .
Proof. Let the neighbors of x be v1 . . . vd s.t. w(x, v1 ) ≥ w(x, v2 ) ≥ . . . ≥ w(x, vd ). Suppose
w(x, vi ) < /dw(x, v1 ), then applying Lemma 8.3 gives a multiplicative error of 1 + /d. Applying
this at most d times gives the approximation ratio, and moves all the light edges onto v1 .
8.1.2

Bounded Weight Vertex Sparsification

The bucketing of vertices in the independent set ensures that all the weights in each bucket are
within a factor O(d/), which will allow us to iteratively reduce the number of vertices by applying
the Sample algorithm given in Section 7 O(log n) times. Note that our Sample algorithm doubles
the weights of each sampled star, so Nxi will denote the star x in ith iteration graph Gi with updated
weights for that graph.
Theorem 8.5. Given a bipartite graph G with bipartition (V C, XG), and weights in [γ, U γ]
where U = O(poly(n)), with degree of x ∈ XG bounded by d, and error . Then there is a
t = O(dU log3 n−2 ) whereby BoundedVertexSparsify(G, V C, XG, t) returns H, s.t. w.h.p.
47

BoundedVertexSparsify(G, VC, XG, t)
Input: Bipartite graph G with bipartition (VC, XG)
1. Initialize G0 ← G, XG0 ← XG, and H ← ∅
2. For each i = 0 to l − 1
(a) Compute a t-bundle vertex set XGlight
⊆ XGi of Gi
i
(b) (Gi+1 , XGi+1 ) ← Sample(Gi , VC, XGi , XGlight
)
i
(c) Add

S

x∈XGlight
i

Nxi to H

3. Return H = H ∪ Gl
Figure 12: Bounded Weight Vertex Sparsification in G
1. H is a bipartition with VC on one side and at most O(|V C|t log n) vertices on the other
2. H ≈V C G
Proof. (1): Set l = O(log n) and note that |XG| ≤ n, so Gl is unlikely to have many remaining
vertices after sampling O(log n) times by a standard argument using concentration bounds. Then,
Lemma 8.8 will show |XGlight
| ≤ t|V C| for all i, giving the desired size.
i
(2): By construction of BoundedVertexSparsify(G, V C, XG), the weights of each Gi are in
[2i γ, 2i γU ]. We will show in Lemma 8.8 that for each Gi and XGi , we can find a t-bundle vertex
set XGlight
of XGi , such that XGheavy
= XGi \ XGlight
is a 2i γ(dU )−1 t − heavy vertex subset.
i
i
i
Assuming that this is the case, from Lemma 7.3, if we set b = l , then with high probability
Gi+1 ∪
Gi ≈bVC


[

Nxi

x∈XGlight
i

By construction, for all j < i, XGlight
∩ XGi = ∅, so adding each
j

S

x∈XGlight
j

Nxj to both sides

will still preserve the relation above. Applying this argument inductively and using b =
H ≈VC
G with high probability.



l

gives

In order to complete the proof of Theorem 8.5, it is now necessary to show that for each Gi
and XGi , we can construct XGlight
such that XGi \ XGlight
is a 2i γ(dU )−1 t − heavy subset of
i
i
light
XGi . The idea will simply be to construct XGi
from t disjoint spanning forests in GiVC with
some additional properties that will allow O(poly(log n, −1 )) dynamic maintenance in the following
subsection.
Definition 8.6. Given G with vertex bipartition (VC, X), we say that F = F1 ∪· . . . ∪· Ft is a t-clique
forest if
1. Each Fi is a forest of GVC and all are disjoint.
48

LightVertices(Gi , VC, XGi )
Input: Bipartite graph Gi with bipartition (VC, XGi )
1. Initialize XGlight
← ∅ and Fi =
i

S

j∈[t] Fi,j

with Fi,j ← ∅ for all j

2. For each j = 1 to t
(a) While some edge ex ∈ GiVC can be added to forest Fi,j
(b) Place ex in Fi,j , place x in XGlight
, and remove Kx from GiVC
i
3. Return XGlight
i
Figure 13: Light Vertex Set of XG
2. For any x ∈ X, at most one edge ex ∈ Kx is in F .
3. For all x ∈ X such that F ∩ Kx = ∅, for any ex = (u, v)x ∈ Kx , u and v are connected in all
Fi
Lemma 8.7. Given G with vertex bipartition (VC, X) such that all x ∈ X have maximum degree d,
weights in [γ, γU ] and a t-clique forest F , if X light = {x ∈ X|F ∩ Kx = ∅}, then X heavy = X \ X light
is an γ(dU )−1 t − heavy subset of X
Proof. For some (u, v)x ∈ Kx with x ∈ X heavy , suppose (u, v)x is in a cut SVC ⊂ VC such that
∆GVC (SVC ) < γ(dU )−1 t. From Lemma 6.10, all edges in GVC have weight at least γ(dU )−1 .
Therefore, there must exist some Fj such that u and v are not connected, giving a contradiction.
Note that after the algorithm terminates GiVC = x∈XGheavy Kx , which will be necessary for the
i
dynamic maintenance. The following lemma follows by construction and the fact that each forest
has at most |V C| − 1 edges.
S

Lemma 8.8. Fi is a t-clique forest of GiVC , |XGlight
| ≤ t|V C|, and XGheavy
is a 2i γ(dU )−1 t−heavy
i
i
subset of XGi
Proof of Theorem 8.1 (1) The first part follows from Theorem 5.1 and the second part follows
from Theorem 8.5
b i from property (2).
b with U = 4d−1 for each G
(2) Property (1) of Theorem 8.2 gives us G ≈/2 G
b i is bipartite, and property (4) implies that each vertex in X G
bi
Then, property (3) implies that each G
−1
V
C
b
b
is bounded by d. We can then apply Theorem 8.5 to each Gi , with U = 4d to get Gi ≈/2 Hi with
high probability. Note that we are implicitly assuming U = O(poly(n)), aka −1 = O(poly(n)). As
was discussed at the end of Section 7, we could avoid this assumption by adding an extra −1 factor
to the t-bundle, but any −1 = ω(poly(n)) loses any practical value. L = O(log W ) = O(poly(log n))
b i , so
by assumption, and property (4) of Theorem 8.2 ensures that a vertex is only sampled in one G

49

b ≈V C H w.h.p. for sufficient constants in t.
taking the union over O(poly(log n)) buckets preserves G
/2
b is a stronger statement than G ≈V C G,
b implying G ≈V C H
G ≈/2 G

/2
(3) Edge weights are only changed in Sample where they are either doubled or left alone.
b giving the appropriate
VertexSparsify calls Sample at most O(log n) times for each bucket of G,
bound.

8.1.3

Improved Static Algorithm for General Graphs

Composing this routine O(log n) times, along with spectral sparsifiers, leads to a static routine:
Corollary 3.2. Given any graph G = (V, E), and a vertex cover VC of G, where X = V \ VC,
with error , we can build an -approximate terminal-cut-sparsifier H with O(|VC| poly(log n, −1 ))
vertices in O(m · poly(log n, −1 )) work.
Now that we have sufficient notation in place, by terminal − cut − sparsif ier, we mean that
G ≈VC
H with high probability. Note that this is almost equivalent to Theorem 8.1, but we make

no assumptions on the degree of vertices in X. Also, we will specify poly(logn , −1 ) as log18 n−7 .
Proof. Consider running the following routine iteratively:
1. Sparsify G with error b =


O(log n)

and output G̃

b ⊆ X whose degree are less
b containing VC and vertices X G
2. Find the bipartite subgraph G
2
−2
b with d = O(log2 n−2 ) and with
b VC, X G,
than O(log n ). Run VertexSparsify on G,

b
error b = O(log
n) , returning H
b and H ← H ∪ H
b
3. G ← G̃ \ G

If at any point, we have |X| < |VC| log17 n−7 , then return H ∪ G.
From [SS11], and the number of edges in G̃ is O(n log nb−2 ) with high probability. Therefore, at
least half of |X| have degree less than O(log2 nb−2 ) because otherwise the number of edges in G̃
would be O(|X| log2 nb−2 ) = O(n log2 nb−2 ) by the assumption |X| ≥ |VC|. This eliminates half the
vertices in X with high probability for every run of the routine, so the process can continue at most
b will have at most O(|VC|t log n) vertices with
O(log n) times. From Theorem 8.1 each bucket of H
3 b−3
2 b−2
2
t = O(d log n ) and d = O(log n ), giving O(|VC| log15 n−7 ). We run sparsification on G
b O(log n) times, so from the guarantees of Theorem 5.1 and property (3)
and VertexSparsify on G
of Theorem 8.1, the weights are within a factor O(nO(log n) ). Therefore, there are at most O(log2 n)
b and at most O(|VC| log17 n−7 ) vertices which has the appropriate size requirement.
buckets of H,
Sparsification gives G ≈b G̃ with high probability, which is a stronger statement than G ≈bVC
G̃.

O(log
n)
VC
b
b
Theorem 8.1, which is still applicable for weight within a factor O(n
), gives G ≈b H with
VC
b
b
high probability. Therefore (G̃ \ G) ∪ H ≈2b G with high probability. Applying this inductively for

O(log n) steps gives the desired relation by setting b = O(log
n) as was done in the iterative routine
above.
Sparsifying G requires O(m · poly(log n, −1 )) work [SS11]. Furthermore, in Section 8.2 we
will show that VertexSparsify can be maintained dynamically in worst-case update time of
O(poly(log n, −1 )), so it’s static runtime must be O(m · poly(log n, −1 )).

50

1. Dynamically maintain a sparsified G, which we will denote G̃
2. Dynamically maintain a branch vertex cover, VC, on G̃, where we ensure s, t ∈ VC
3. Dynamically maintain a vertex sparsified G̃ using VC and X G̃ = V \ VC which we will
denote H
4. Every 2 ∆H (SbVH ) dynamic steps, recompute SbVH ⊂ VH , an approximate minimum s − t
cut on H, ignoring all degree zero vertices

Figure 14: Dynamic (1 + )-approximate Minimum s − t Cut

8.2

Dynamic Minimum Cut of Bipartite Graphs

Now that we have the full process of VertexSparsify, we will give the dynamic algorithm for
maintaining a (1+)-approximate minimum cut in amortized O(poly(log n, −1 )) time. The algorithm
in Figure 14 will be analogous to the one given in Section 6, but will replace sparsification of GVC
with VertexSparsify, improving the approximation by a factor of 2.
In this algorithm we run into the same issue of returning a cut of size O(n) in amortized
O(poly(log n, −1 )) time, and will allow a similar querying scheme. Let VH be the non-zero degree
vertex set of H. Our vertex sparsification process ensures that VC ⊆ VH , so for the computed
SbVH ⊂ VH , we will maintain the cut SbVH ∩ VC ⊂ VC with s ∈ SbVH . For a vertex v ∈ VC, return
v is with s iff v ∈ SbVH ∩ VC, which takes O(1) time. For a vertex x ∈
/ VC, note that all of N (x)
must be in VC, and return that x is with s iff w(x, SbVH ∩ VC) = w(x) (SbVH ∩ VC) in G̃, taking
O(poly(log n, −1 )) time to compute w(x, SbVH ∩ VC) and w(x) (SbVH ∩ VC), by Corollary 5.2 and
Corollary 6.4. Note that by restricting to VC we will be able take advantage of the approximation
guarantees of vertex sparsification in the corollary below.
Corollary 8.9. The dynamic algorithm maintains a (1 + )-approximate minimum s − t cut in G,
and will only compute an approximate minimum s − t cut on H every O(OP T ) dynamic steps,
taking O(OP T · poly(log n, −1 )) time each computation
Proof. G̃ = F1 ∪· . . . ∪· FK for some K = O(poly(log n, −1 )) by Corollary 5.2, so from Lemma 3.1
and Corollary 6.4, we know |VC| = O(OP T · poly(log n, −1 )) and the degree of all vertices in X G̃
is O(poly(log n, −1 )). From Corollary 5.2, the weights of G̃ are in [1, O(n)], and so property (1) of
Theorem 8.1 implies that H has O(OP T · poly(log n, −1 )) edges. Therefore, we can find a (1 + b)
approximate minimum s − t cut in H, in O(OP T · poly(log n, −1 )) time.

Assume SbVH ⊂ VH is returned as a (1 + b)-approximate minimum s − t cut in H, with b = O(1)
.
Let SbVC = SbVH ∩ VC be its restriction to VC, and let
Sb = SbV C ∪ {x ∈ X G̃ : w(x, SbV C ) = w(x) (SbV C )}
be the extension of SbVC onto G̃, which is the cut returned by our vertex querying scheme. From
Corollary 5.2 and Theorem 8.1, we have G ≈b G̃ and G̃ ≈bVC
H, respectively, which gives

b ≤ (1 + b)∆ (S)
b = (1 + b)∆ (SbV C ) ≤ (1 + b)2 ∆H (SbV C ).
∆G (S)
G̃
G̃

51

On the other hand, let S ⊂ V be the minimum s − t cut in G, and S V C ⊂ VC be its restriction
to VC. Using the fact that ∆G̃ (S VC ) is the weight of the minimal extension of S VC in G̃, along with
the approximations G ≈b G̃ and G̃ ≈bVC
H gives

∆G (S) ≥ (1 − b)∆G̃ (S) ≥ (1 − b)∆G̃ (S V C ) ≥ (1 − b)2 ∆H (S V C ).
The near-optimality of SbVH on H and setting SbVC = SbVH ∩ VC, gives,
∆H (S V C ) ≥ (1 − b)∆H (SbVH ) ≥ (1 − b)∆H (SbVC )
b ≤ (1 + b)5 ∆G (S), and by choosing b =  we maintain a (1 +  )-approximate
Therefore, ∆G (S)
2
O(1)
minimum s − t cut in G.
An approximate minimum s − t cut on H will be re-computed in 2 ∆H (SbVH ) dynamic steps.
OP T = ∆G (S) ≤ (1 + )∆H (SbVH ), so ∆H (SbVH ) = O(OP T )

All that is left to be shown is that data structures can be maintained in O(poly(log n, −1 )) time
per dynamic update. As a result of Corollary 5.2, it suffices to show the following
b H, and VC takes
Theorem 8.10. For each addition/deletion of an edge in G̃, maintaining G,
−1
O(poly(log n,  )) time.

As in Section 6.3, most of the necessary analysis for Theorem 8.10 will follow from the fact that
all x ∈ X G̃ have degree O(poly(log n, −1 )), and the only substantial changes made to the data
structures in one dynamic step, are done within the neighborhood of some x ∈ X G̃. We will also
assume all of the dynamic data structure analysis of Section 6.3 with regards to maintaining a
corresponding GVC of some G.
In the rest of this section, we will first examine dynamically maintaining the pre-processing
routine, particularly when vertices are moved in and out of the vertex cover. Then we will consider
dynamically maintaining our vertex sparsification routine. Most of the time complexity analysis
will follow from Section 6.3, and the only tricky part will be ensuring that dynamic changes do not
multiply along iterations of the sparsification routine.
b As with the multi-graph GVC , for G
b \ X G̃, an edge e denotes an edge originally
Maintaining G
∅
b
in G̃ and ex denotes an edge that was moved into G \ X G̃ from Nx . For each x ∈ X G̃, let xmax
denote the vertex such that (x, xmax ) has the maximum weight in Nx . Let bucket(x) be the i ∈ [L]
such that w(x, xmax ) ∈ [2i−1 , 2i ]. We can use 1 as our scalar here because all weights of G are 1,
so from Corollary 5.2, all weights of G̃ are in [1, O(n)]. In order to maintain each xmax , we will
assume that the data structure of G̃ is such that the adjacency list of each x is sorted by edge
weight. Consequently, edge insertions/deletions in G̃ will require O(log n) time.
Maintaining each bucket for an edge insertion/deletion in G̃ will be analogous to maintaining
GVC in Section 6.3. We will first show that moving a vertex in and out of X G̃ can be done in
O(poly(log n, −1 )) time, then give the overall update process, which will primarily just be composed
of these two operations.
b X G̃, v) will output G
b with v ∈ VC
Lemma 8.11. If v is not in VC, then running RemoveXG(G,
in O(degv log n) time, where degv is the degree of v in G̃

Proof. Costs of the three steps are:
52

RemoveXG(G̃, X G̃, v)
b \ X G̃
1. Delete all edges ev incident to vmax from G
b
2. Delete all edges incident to v from G
bucket(v)
b \ X G̃
3. For all edges e incident to v in G̃, add e∅ into G

Figure 15: Removing a Vertex from X G̃

b X G̃, v)
InsertXG(G,
b \ X G̃
1. Delete all edges e∅ incident to v in G

2. For all edges e = (v, w) ∈ G̃ incident to v
b \ X G̃
(a) If w(v, w) < d w(v, vmax ): insert (w, vmax )v into G
b
(b) Otherwise: insert (v, w) into G
bucket(v)

Figure 16: Inserting a Vertex into X G̃
b \ X G̃ takes O(log n) time per deletion and
1. Deleting all edges ev incident to vmax from G
O(degv ) deletions.
b
2. Deleting all edges incident to v from G
bucket(v) takes O(log n) time per deletion and O(degv )
deletions.
b \ X G̃ takes O(log n) time and is done for all edges e incident to v in G̃, so
3. Adding e∅ into G
O(degv ) times

If v is not in VC, then v cannot be incident to any vertices in X G̃. Therefore, placing v in
b k and no edges ev exist in G
b \ X G̃.
VC implies that v cannot be incident to any edges in all G
b
RemoveXG(G, X G̃, v) performs exactly these removals and inserts all necessary e∅ incident to v
b \ X G̃
into G

b then running InsertXG(G,
b X G̃, v)
Lemma 8.12. If v is not in VC, but was placed in VC for G,
b
will output G with v ∈
/ VC in O(degv log n) time, where degv is the degree of v in G̃

Proof. Costs of the two steps are:
b \ X G̃ takes O(log n) time per deletion and O(degv )
1. Deleting all edges e∅ incident to v in G
deletions.

53

b \ X or inserting (v, w) into
2. Checking if w(v, w) < d w(v, vmax ) and inserting (w, vmax )v into G
b
G
bucket(v) takes O(log n) time. This is done for all edges e = (v, w) ∈ G̃ incident to v, so
O(degv ) times
b then only edges e are incident to v in G.
b
If v is not in VC, but was placed in VC for G,
∅
Removing v from VC requires deleting all of these edges. Further, all edges e in Nv of sufficiently
b \ X G̃ as ev , and the rest of Nv must be placed in the appropriate
small weight must be moved to G
b
b
Gi . InsertXG(G, X G̃, v) performs exactly these operations.
b for each e = (u, v) insertion/deletion in G̃ will then be as
The full dynamic update process of G
follows.
b X G̃, v) if v ∈
1. For u and v, RemoveXG(G,
/ VC

2. Update VC and G̃ as done in section 5
b \ X G̃
3. Add/delete (u, v)∅ from G

4. Update umax and vmax , which will simply require looking at the first edge incident to u and v
in G̃, as the list is sorted by weight
b X G̃, v) if v ∈
5. For u and v, InsertXG(G,
/ VC
b =G
b \ X G̃ ∪
b1 ∪
bL
Lemma 8.13. For each edge addition/deletion in G̃, maintaining G
· G
· . . . ∪· G
takes O(poly(log n, −1 )) time.
b X G̃, v) and RemoveXG(G,
b X G̃, v) are only performed if v ∈
Proof. Note that InsertXG(G,
/ VC,
−1
which implies that the degree of v in G̃ is O(poly(log n,  )). Updating VC and G̃ is known to take
O(poly(log n, −1 )) time. Steps 3 and 4 clearly take O(log n) time. Therefore, the full runtime of
this update process is O(poly(log n, −1 )).

b \ X G̃
Maintaining BoundedVertexSparsify We will dynamically sparsify the multi-graph G
−1
b
as per usual, so each edge insertion/deletion requires O(poly(log n,  )) update time for G\X
G̃. Accordingly, we will only consider maintaining the necessary data structures for BoundedVertexSparsify
b k , which we will simply denote as G with bipartition (VC, XG).
of each G
Alterations to G are made by the dynamic update process in the previous section, which
implies that we only need to consider the following changes to G. Add/Delete a vertex x from
X, and add/delete Nx from G. Add/Delete an edge within Nx for some x ∈ X. If an edge
is added/deleted from Nx , we will simply delete Nx from G, and then add Nx with the edge
added/deleted to G. Accordingly, in order to establish that our data structures can be maintained
in O(poly(log n, −1 )) update time, we just need to show that adding/deleting any Nx from G can
be done in O(poly(log n, −1 )) update time.
For each level i of computing a light vertex set and running Sample, we need to maintain Gi ,
i
GVC , XGlight
and all Fi,j in Fi . The data structures for Gi and GiVC will be as in Subsection 6.3.
i
Assume that the data structure of each Fi,j is such that we can search for edges in O(log n)-time,
either by search trees or linked lists with back pointers (see e.g. [CLR+ 09], Chapters 10.2, 10.3, and

54

InsertStar(Gi , XGi , XGlight
, Nx )
i
1. Update Gi ← Gi ∪ Nx , XGi ← XGi ∪ x, and insert Kx into GiVC
2. For the first ex ∈ Kx that can be added to some Fi,j : Update Fi,j ← Fi,j ∪ ex , XGlight
←
i
light
i
XGi
∪ x, and remove Kx from GVC
3. If no ex ∈ Kx can be added to any Fi,j ,
InsertStar(Gi+1 , XGi+1 , XGlight
i+1 , 2Nx )

with probability

1
2:

run

Figure 17: Add Nx to Gi
13). The data structure each XGlight
will just be a list of vertices with insertion/deletion taking
i
O(log n) time.
We will still assume edge additions/deletions in Gi , GiVC can be maintained in O(poly(log n, −1 )),
as was shown in Subsection 6.3. Most of the time complexity analysis will then follow from this,
and we just need to establish that the additions/deletions will not multiply as we move down the
pipeline. This will ultimately follow from our construction of the t-clique forests.
Adding some Nx to Gi
corresponding Nx .

The algorithm in Figure 17 will add a vertex x to Gi , along with the

, Nx ) adds Nx to Gi while maintaining t-clique forest
Lemma 8.14. InsertStar(Gi , XGi , XGlight
i
Fi
Proof. If some ex ∈ Kx can be added to some Fi,j , then by construction, Fi ∩ Kx = ex and
x ∈ XGlight
. Therefore, Fi is still a t-clique forest, and x ∈ XGlight
implies x ∈
/ XGi+1 , so it is only
i
i
light
necessary to add ex to Fi,j and x to XGi .
If no ex ∈ Kx can be added to any Fi,j , then Fi ∩ Kx = ∅ and x ∈ XGheavy
. Therefore, Fi is
i
heavy
still a t-clique forest, and x ∈ XGi
implies a coin must be flipped to determine whether x is
added to XGi+1 and 2Nx is added to Gi+1 .
Furthermore, we still maintain GiVC =
Deleting some Nx from Gi
with the corresponding Nx .

S

x∈XGheavy
i

Kx

The algorithm in Figure 18 will delete a vertex x from Gi , along

Lemma 8.15. RemoveStar(Gi , XGi , XGlight
, Nx ) removes Nx from Gi while maintaining t-clique
i
forest Fi
Proof. If we had Fi ∩ Kx = ex , then x was in XGlight
, so ex must be removed from some Fi,j and x
i
S
light
must be removed from XGi . Fi was a t-clique forest and GiVC = x∈XGheavy Kx (as was noted),
i

implying that multiple edges in GiVC cannot be added to Fi,j without creating a cycle. If fy is added

55

RemoveStar(Gi , XGi , XGlight
, Nx )
i
1. Update Gi ← Gi \ Nx , XGi ← XGi \ x, and remove Kx from GiVC
2. If some ex is in some Fi,j
(a) Update Fi,j ← Fi,j \ ex , XGlight
← XGlight
\x
i
i
(b) If some edge fy ∈ GiVC can be added to Fi,j
• Update Fi,j ← Fi,j ∪ fy , XGlight
← XGlight
∪ y, and remove Ky from GiVC
i
i
• run RemoveStar(Gi+1 , XGi+1 , XGlight
i+1 , 2Ny ) if y ∈ XGi+1
3. If no ex ∈ Kx is in any Fi,j , run RemoveStar(Gi+1 , XGi+1 , XGlight
i+1 , 2Nx ) if x ∈ XGi+1

Figure 18: Remove Nx from Gi
to Fi,j then y is added to XGlight
and Fi ∩ Ky = fy . Therefore, Fi is still a t-clique forest, and
i
light
because y ∈ XGi , it is now necessary to remove 2Ny from Gi+1 if y ∈ XGi+1 .
If we have Fi ∩ Kx = ∅, then x ∈ XGheavy
and Fi is still a t-clique forest. Further XGi+1 ⊆ XGi ,
i
so it is necessary to remove 2Nx from Gi+1 if x ∈ XGi+1 .
Furthermore, we still maintain GiVC =

S

x∈XGheavy
i

Kx

Lemma 8.16. For any addition/deletion of some x from XG0 and Nx from G0 , maintaining H
takes O(t · poly(log n, −1 )) time
Proof. Checking each forest for an edge insertion/deletion takes O(t log n) time. It follows almost
immediately from the analysis in Subsection 6.3 that the rest of the computation in one iteration
of InsertStar and RemoveStar takes O(poly(log n, −1 )) time. Furthermore, both can make at
most one recursive call to themselves, so adding/deleting Nx from G0 takes O(l · t · poly(log n, −1 ))
time where l = O(log n).

Proof of Theorem 8.10 : Any edge insertion/deletion in G̃ requires O(poly(log n, −1 )) update
b and VC from Lemma 8.13. Therefore, there are at most O(poly(log n, −1 )) additime for G
b i , which will require O(t · poly(log n, −1 )) update time from
tions/deletions of some Nx to some G
Lemma 8.16, where t = O(poly(log n, −1 )). Thus, the full dynamic update process of all data
structures takes O(poly(log n, −1 )) time per dynamic update of G̃.

References
[ACD+ 16]

Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, and Renato F.
Werneck. “On Dynamic Approximate Shortest Paths for Planar Graphs with WorstCase Costs”. In: Symposium on Discrete Algorithms (SODA). 2016, pp. 740–753 (cit. on
p. 1).
56

[ACL06]

Reid Andersen, Fan Chung, and Kevin Lang. “Local Graph Partitioning using PageRank
Vectors”. In: Symposium on Foundations of Computer Science (FOCS). 2006, pp. 475–
486 (cit. on p. 1).

[AG09]

Kook Jin Ahn and Sudipto Guha. “Graph Sparsification in the Semi-streaming Model”.
In: International Colloquium on Automata, Languages, and Programming (ICALP).
2009, pp. 328–338 (cit. on p. 7).

[AGK14]

Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. “Towards (1+ )-Approximate
Flow Sparsifiers”. In: Symposium on Discrete Algorithms (SODA). 2014, pp. 279–293
(cit. on pp. 2, 10, 11, 39, 40).

[AGM12a]

Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. “Analyzing graph structure via
linear measurements”. In: Symposium on Discrete Algorithms (SODA). 2012, pp. 459–
467 (cit. on p. 7).

[AGM12b]

Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. “Graph sketches: sparsification,
spanners, and subgraphs”. In: Symposium on Principles of Database Systems (PODS).
2012, pp. 5–14 (cit. on p. 7).

[AGM13]

Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. “Spectral Sparsification in Dynamic Graph Streams”. In: Workshop on Approximation Algorithms for Combinatorial
Optimization Problems (APPROX). 2013, pp. 1–10 (cit. on p. 5).

[AP09]

Reid Andersen and Yuval Peres. “Finding Sparse Cuts Locally Using Evolving Sets”.
In: Symposium on Theory of Computing (STOC). 2009, pp. 235–244 (cit. on p. 1).

[AVW14]

Amir Abboud and Virginia Vassilevska Williams. “Popular conjectures imply strong
lower bounds for dynamic problems”. In: Symposium on Foundations of Computer
Science (FOCS). 2014, pp. 434–443 (cit. on p. 1).

[BBC+ 12]

Christian Borgs, Michael Brautbar, Jennifer Chayes, and Shang-Hua Teng. “A Sublinear
Time Algorithm for PageRank Computations”. In: Algorithms and Models for the Web
Graph. Springer, 2012, pp. 41–53 (cit. on p. 1).

[BGS15]

Surender Baswana, Manoj Gupta, and Sandeep Sen. “Fully Dynamic Maximal Matching
in O(log n) Update Time”. In: SIAM Journal on Computing 44.1 (2015). Announced
at FOCS’11, pp. 88–113 (cit. on pp. 1, 9).

[BHI15]

Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. “Deterministic Fully
Dynamic Data Structures for Vertex Cover and Matching”. In: Symposium on Discrete
Algorithms (SODA). 2015, pp. 785–804 (cit. on p. 1).

[bHS16]

Marcel K. de bSilva, Nicholas J. A. Harvey, and Cristiane M. Sato. “Sparse Sums of
Positive Semidefinite Matrices”. In: ACM Transactions on Algorithms 12.1 (2016), p. 9
(cit. on p. 5).

[BK15]

András A. Benczúr and David R. Karger. “Randomized Approximation Schemes for
Cuts and Flows in Capacitated Graphs”. In: SIAM Journal on Computing 44.2 (2015),
pp. 290–319 (cit. on pp. 1, 4, 7, 27, 40).

[BKS12]

Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. “Fully Dynamic Randomized
Algorithms for Graph Spanners”. In: ACM Transactions on Algorithms 8.4 (2012).
Announced at ESA’06 and SODA’08, 35:1–35:51 (cit. on pp. 1, 6, 12, 13, 16–19, 22).

57

[BS16]

Aaron Bernstein and Cliff Stein. “Faster Fully Dynamic Matchings with Small Approximation Ratios”. In: Symposium on Discrete Algorithms (SODA). 2016, pp. 692–711
(cit. on p. 9).

[BSS+ 13]

Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. “Spectral
Sparsification of Graphs: Theory and Algorithms”. In: Communications of the ACM
56.8 (2013), pp. 87–94 (cit. on pp. 1, 5).

[CCL+ 15]

Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. “Efficient
Sampling for Gaussian Graphical Models via Spectral Sparsification”. In: Conference
on Learning Theory (COLT). 2015, pp. 364–390 (cit. on p. 1).

[CLR+ 09]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009 (cit. on p. 54).

[DDH09]

John Dabney, Brian C. Dean, and Stephen T. Hedetniemi. “A Linear-Time Algorithm
for Broadcast Domination in a Tree”. In: Networks 53.2 (2009), pp. 160–169 (cit. on
p. 64).

[EES+ 08]

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. “Lower-stretch
spanning trees”. In: SIAM Journal on Computing 38.2 (2008), pp. 608–628 (cit. on
p. 2).

[ES81]

Shimon Even and Yossi Shiloach. “An On-Line Edge-Deletion Problem”. In: Journal of
the ACM 28.1 (1981), pp. 1–4 (cit. on p. 17).

[FHH+ 11]

Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi. “A
General Framework for Graph Sparsification”. In: Symposium on Theory of Computing
(STOC). 2011, pp. 71–80 (cit. on pp. 7, 10, 25, 40, 41, 44).

[GKK+ 15]

David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. “Dynamic graph
connectivity with improved worst case update time and sublinear space”. In: CoRR
abs/1509.06464 (2015) (cit. on p. 27).

[GP13]

Manoj Gupta and Richard Peng. “Fully Dynamic (1 + )-Approximate Matchings”. In:
Symposium on Foundations of Computer Science (FOCS). 2013, pp. 548–557 (cit. on
p. 9).

[GS09]

Manoj Gupta and Ankit Sharma. “An O(log(n)) Fully Dynamic Algorithm for Maximum
matching in a tree”. In: CoRR abs/0901.2900 (2009) (cit. on pp. 33, 64).

[GT12]

Shayan Oveis Gharan and Luca Trevisan. “Approximating the Expansion Profile and
Almost Optimal Local Graph Clustering”. In: Symposium on Foundations of Computer
Science (FOCS). 2012, pp. 187–196 (cit. on p. 1).

[Har12]

Nick Harvey. Matrix Concentration and Sparsification. Workshop on “Randomized
Numerical Linear Algebra (RandNLA): Theory and Practice”. 2012 (cit. on p. 15).

[HK99]

Monika Rauch Henzinger and Valerie King. “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation”. In: Journal of the ACM 46.4 (1999).
Announced at STOC’95, pp. 502–516 (cit. on p. 1).

[HKN+ 15]

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. “Unifying and Strengthening Hardness for Dynamic Problems via the Online
Matrix-Vector Multiplication Conjecture”. In: Symposium on Theory of Computing
(STOC). 2015, pp. 21–30 (cit. on p. 1).
58

[HLT01]

Jacob Holm, Kristian Lichtenberg, and Mikkel Thorup. “Poly-Logarithmic Deterministic
Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and
Biconnectivity”. In: Journal of the ACM 48.4 (2001). Announced at STOC’98, pp. 723–
760 (cit. on pp. 1, 8, 24, 28).

[JK15]

Gorav Jindal and Pavel Kolev. “Faster Spectral Sparsification of Laplacian and SDDM
Matrix Polynomials”. In: CoRR abs/1507.07497 (2015) (cit. on p. 1).

[Kar00]

David R. Karger. “Minimum Cuts in Near-linear Time”. In: Journal of the ACM 47.1
(2000). Announced at STOC’96, pp. 46–76 (cit. on p. 9).

[KK15]

Dmitry Kogan and Robert Krauthgamer. “Sketching Cuts in Graphs and Hypergraphs”.
In: Conference on Innovations in Theoretical Computer Science (ITCS). 2015, pp. 367–
376 (cit. on p. 10).

[KKM13]

Bruce M. Kapron, Valerie King, and Ben Mountjoy. “Dynamic graph connectivity
in polylogarithmic worst case time”. In: Symposium on Discrete Algorithms (SODA).
2013, pp. 1131–1142 (cit. on pp. 1, 2, 7, 8, 24, 27).

[KL13]

Jonathan A. Kelner and Alex Levin. “Spectral Sparsification in the Semi-streaming
Setting”. In: Theory of Computing Systems 53.2 (2013). Announced at STACS’11,
pp. 243–262 (cit. on pp. 1, 5).

[KLM+ 14]

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron
Sidford. “Single Pass Spectral Sparsification in Dynamic Streams”. In: Symposium on
Foundations of Computer Science (FOCS). 2014, pp. 561–570 (cit. on pp. 1, 5).

[KLO+ 14]

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. “An AlmostLinear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its
Multicommodity Generalizations”. In: Symposium on Discrete Algorithms (SODA).
2014, pp. 217–226 (cit. on pp. 1, 9, 11, 32).

[KLP12]

Ioannis Koutis, Alex Levin, and Richard Peng. “Improved Spectral Sparsification and
Numerical Algorithms for SDD Matrices”. In: Symposium on Theoretical Aspects of
Computer Science (STACS). 2012, pp. 266–277 (cit. on p. 1).

[KLP+ 16]

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman.
“Sparsified Cholesky and Multigrid Solvers for Connection Laplacians”. In: Symposium
on Theory of Computing (STOC). 2016, pp. 842–850 (cit. on pp. 1, 5, 10).

[KOS+ 13]

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. “A
simple, combinatorial algorithm for solving SDD systems in nearly-linear time”. In:
Symposium on Theory of Computing (STOC’13). 2013, pp. 911–920 (cit. on p. 5).

[Kou14]

Ioannis Koutis. “Simple parallel and distributed algorithms for spectral graph sparsification”. In: Symposium on Parallelism in Algorithms and Architectures (SPAA). 2014,
pp. 61–66 (cit. on pp. 1, 5, 7, 13, 15).

[KRS+ 15]

Rasmus Kyng, Anup Rao, Sushant Sachdeva, and Daniel A. Spielman. “Algorithms
for Lipschitz Learning on Graphs”. In: Conference on Learning Theory (COLT). 2015,
pp. 1190–1223 (cit. on p. 1).

[KW14]

Michael Kapralov and David P. Woodruff. “Spanners and sparsifiers in dynamic streams”.
In: Symposium on Principles of Distributed Computing (PODC). 2014, pp. 272–281
(cit. on p. 5).
59

[LS13]

Yin Tat Lee and Aaron Sidford. “Efficient Accelerated Coordinate Descent Methods
and Faster Algorithms for Solving Linear Systems”. In: Symposium on Foundations of
Computer Science (FOCS). 2013, pp. 147–156 (cit. on p. 5).

[LS15]

Yin Tat Lee and He Sun. “Constructing Linear-Sized Spectral Sparsification in AlmostLinear Time”. In: Symposium on Foundations of Computer Science (FOCS). 2015,
pp. 250–269 (cit. on pp. 1, 5).

[Mad10]

Aleksander Mądry. “Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs”. In: Symposium on Foundations of Computer Science (FOCS). 2010,
pp. 245–254 (cit. on p. 1).

[NS13]

Ofer Neiman and Shay Solomon. “Simple Deterministic Algorithms for Fully Dynamic
Maximal Matching”. In: Symposium on Theory of Computing (STOC). 2013, pp. 745–
754 (cit. on pp. 1, 2, 9, 11).

[OR10]

Krzysztof Onak and Ronitt Rubinfeld. “Maintaining a Large Matching and a Small
Vertex Cover”. In: Symposium on Theory of Computing (STOC). 2010, pp. 457–464
(cit. on pp. 1, 9).

[OSV12]

Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. “Approximating the
Exponential, the Lanczos Method and an Õ(m)-Time Spectral Algorithm for Balanced
Separator”. In: Symposium on Theory of Computing (STOC). 2012, pp. 1141–1160
(cit. on p. 1).

[OV11]

Lorenzo Orecchia and Nisheeth K. Vishnoi. “Towards an SDP-based Approach to
Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition”. In: Symposium on Discrete Algorithms (SODA). 2011, pp. 532–545 (cit. on
p. 1).

[Pat10]

Mihai Pǎtraşcu. “Towards Polynomial Lower Bounds for Dynamic Problems”. In:
Symposium on Theory of Computing (STOC). 2010, pp. 603–610 (cit. on p. 1).

[Pen16]

Richard Peng. “Approximate Undirected Maximum Flows in O(m polylog n) Time”. In:
Symposium on Discrete Algorithms (SODA). 2016, pp. 1862–1867 (cit. on pp. 1, 32).

[PS14]

Richard Peng and Daniel A. Spielman. “An Efficient Parallel Solver for SDD Linear
Systems”. In: Symposium on Theory of Computing (STOC). 2014, pp. 333–342 (cit. on
pp. 1, 5).

[PS16]

David Peleg and Shay Solomon. “Dynamic (1 + )-Approximate Matchings: A DensitySensitive Approach”. In: Symposium on Discrete Algorithms (SODA). 2016, pp. 712–729
(cit. on pp. 2, 9, 11).
√
Jonah Sherman. “Breaking the Multicommodity Flow Barrier for O( log n)-Approximations
to Sparsest Cut”. In: Symposium on Foundations of Computer Science (FOCS). 2009,
pp. 363–372 (cit. on p. 1).

[She09]

[She13]

Jonah Sherman. “Nearly Maximum Flows in Nearly Linear Time”. In: Symposium on
Foundations of Computer Science (FOCS). 2013, pp. 263–269 (cit. on pp. 1, 32).

[SS11]

Daniel A. Spielman and Nikhil Srivastava. “Graph Sparsification by Effective Resistances”. In: SIAM Journal on Computing 40.6 (2011). Announced at STOC’08,
pp. 1913–1926 (cit. on pp. 2, 4, 5, 50).

60

[ST11]

Daniel A. Spielman and Shang-Hua Teng. “Spectral Sparsification of Graphs”. In: SIAM
Journal on Computing 40.4 (2011). Announced at STOC’04, pp. 981–1025 (cit. on
pp. 1, 5).

[ST13]

Daniel A. Spielman and Shang-Hua Teng. “A Local Clustering Algorithm for Massive
Graphs and Its Application to Nearly Linear Time Graph Partitioning”. In: SIAM
Journal on Computing 42.1 (2013), pp. 1–26 (cit. on p. 1).

[ST14]

Daniel A. Spielman and Shang-Hua Teng. “Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems”. In: SIAM
Journal on Matrix Analysis and Applications 35.3 (2014), pp. 835–885 (cit. on p. 1).

[Tho07]

Mikkel Thorup. “Fully-Dynamic Min-Cut”. In: Combinatorica 27.1 (2007). Announced
at STOC’01, pp. 91–127 (cit. on p. 9).

[TK00]

Mikkel Thorup and David R. Karger. “Dynamic Graph Algorithms with Applications”.
In: Scandinavian Workshop on Algorithm Theory (SWAT). 2000, pp. 1–9 (cit. on p. 9).

[Tro12]

Joel A. Tropp. “User-Friendly Tail Bounds for Sums of Random Matrices”. In: Foundations of Computational Mathematics 12.4 (2012), pp. 389–434 (cit. on pp. 4, 6, 15,
43).

[ZLO15]

Zeyuan Allen Zhu, Zhenyu Liao, and Lorenzo Orecchia. “Spectral Sparsification and
Regret Minimization Beyond Matrix Multiplicative Updates”. In: Symposium on Theory
of Computing (STOC). 2015, pp. 237–245 (cit. on pp. 1, 5).

[Zou12]

Anastasios Zouzias. “A Matrix Hyperbolic Cosine Algorithm and Applications”. In:
International Colloquium on Automata, Languages, and Programming (ICALP). 2012,
pp. 846–858 (cit. on p. 5).

61

A

Omitted Proofs of Section 4.2

In the following we give the omitted proofs of section Section 4.2, which mainly use standard
arguments.
Lemma 4.5. The output H of Light-Spectral-Sparsify is a (1 ± )-spectral sparsifier with
probability at least 1 − n−(c+1) for any input graph G that is independent of the random choices of
the algorithm.
Proof. Let
2
.
3(c + 1) ln n

R=

For every edge e ∈ G \ B, let Xe be the random variable that is 4wG (e) · Le with probability 1/4
and 0 with probability 3/4. We further set LB (j) for every 1 ≤ j ≤ d1/Re as follows:
(

LB (j) =
i

R · LBi
LBi − b1/RcR · LBi

Note that this definition simply guarantees that

if 1 ≤ j ≤ b1/Rc
if j = d1/Re

Pd1/Re
j=1

LB (j) = LBi and LB (j) ≤ R · LBi for
i

every 1 ≤ j ≤ d1/Re. We now want to apply Theorem 4.4 with the random variables Y =
P
Pd1/Re
e∈G\B Xe +
j=1 LB (j) and Z = LG . Observe that


E [Y ] = E 



d1/Re

X

Xe +

X

LB (j) 

j=1

e∈G\B

d1/Re

=

X

E [Xe ] +

X

LB (j)

j=1

e∈G\B

=

X

Le + LB = LG = Z .

e∈G\B

For every edge e ∈ G \ B, using Lemma 4.3, we have
Xe  4wG (e) · Le 

α
· L G ≤ R · LG .
t

Furthermore, using B  G, we have
LB (j) ≤ R · LBi  R · LGi−1
i

for every 1 ≤ j ≤ d1/Re. Thus, the preconditions of Theorem 4.4 are satisfied. We conclude that
we have LGH  (1 + )LG with probability at least
n · exp(−2 /2R) ≥ n · exp((c + 1) ln n) = 1/nc+1 .
A symmetric argument can be used for (1 − )LG  LH .
Lemma 4.6. The output H of algorithm Spectral-Sparsify is a (1 ± )-spectral sparsifier with
probability at least 1 − 1/nc+1 for any input graph G that is independent of the random choices of
the algorithm.
62

Proof. Note that since H =

Sk

i=1 Bi

∪ Gk we have
LH = LGk +

k
X

LBi .

i=1

We now prove by induction on j that LGk + ki=k−j+1 LBi  (1 + /(2k))j LGk−j . This claim is
trivially true for j = 0. For 1 ≤ j ≤ k, we use the induction hypothesis and Lemma 4.5, which both
hold with high probability, to get
P

LGk +

k
X

k
X

LBi = LGk +

LBi + LBk−j+1

i=k−j+2
j−1

i=k−j+1

 (1 + /(2k))

 (1 + /(2k))

j−1

LGk−j+1 + LBk−j+1
(LGk−j+1 + LBk−j+1 )

 (1 + /(2k))j LGk−j .
We now have LH  (1 + /(2k))k LG with high probability by setting j = k. Using symmetric
arguments we can prove (1 − /(2k))k LG  LH . Since (1 − /(2k))k ≥ 1 −  and (1 + /(2k))k ≤ 1 + ,
the claim follows.
Lemma 4.7. With probability at least 1−2n−c , the number of iterations before algorithm SpectralSparsify terminates is
min{dlog ρe, dlog m/((c + 1) log n)e}.
Moreover the size of H is



X

O

|Bi | + m/ρ + c log n ,

1≤j≤i

and the size of the third output of the graph is at most max{O(c log n), O(m/ρ)}.
Proof. We will show that, with probability 1 − 2n−c+1 , every iteration j computes a graph Gj+1
with half the number of edges in Gj . By a union bound, the probability that this fails to be true for
any j < n is at most 2n−c . This implies all claims.
P
We use the following standard Chernoff bound: Let X = N
k=1 Xk , where Xk = 1 with probability
P
pk and Xk = 0 with probability 1 − pk , and all Xk are independent. Let µ = E [X] = N
k=1 pk .
δ2
Then P [X ≥ (1 + δ)µ] ≤ exp(− 2+δ µ) for all δ > 0.
We apply this bound on the output of Light-Spectral-Sparsify for every j. Concretely,
we assign a random variable to each edge e of Gj , with Xe = 1 if and only if e is added to Gj+1 .
Then E [X] = N/4. By construction, the number of edges in Gj is N ≥ (c + 1) log n. Applying the
Chernoff bound with δ = 2 we get
P [X ≥ 2N ] ≤

1
eN/4

≤

1
e((c+1) log n)/4

63

=

1
e1/4 nc+1

≤

1
.
2nc+1

B

Guarantees of Combinatorial Reductions

We show some of the structural results necessary for the reductions in Sections 6, 7, and 8. We first
show the guarantees of Kx :
Proof. (of Theorem 6.9) For any x ∈ X and SVC ⊂ VC, let wKx (SVC ) denote the weight of cutting
P
SVC in Kx . Consequently, for any SVC ⊂ VC, ∆GVC (SVC ) = ∆G\X (SVC ) + x∈X wKx (SVC ), and it
suffices to show that for all x ∈ X, 21 w(x) (SVC ) ≤ wKx (SVC ) ≤ w(x) (SVC ).
Lemma B.1. For any x ∈ X and S ⊂ VC, we have 12 wKx (S) ≤ w(x) (S) ≤ wKx (S)
Proof. Without loss of generality, assume w(x, S) ≤ w(x, VC \ S), so w(x) (S) = w(x, S) =
u∈S∩N (x) w(x, u)

P

X

wKx (S) =

X

X
w(x, VC \ S)
w(x, u)w(x, v)
=
w(x, u) P
w(x,
i)
i∈N (x)
i∈N (x) w(x, i)
u∈S∩N (x)

P
u∈S∩N (x) v∈(VC\S)∩N (x)

where by definition

P

i∈N (x) w(x, i)

= w(x, S) + w(x, VC \ S) and so by assumption
1
w(x, VC \ S)
≤P
≤1
2
i∈N (x) w(x, i)

Proof. (of Lemma 6.10) Each edge in (u, v)x ∈ GVC has weight
w(x, v)w(x, u)
w(u,v)x = P
i∈N (x) w(x, i)
, w(x, v)w(x, u) ≥ γ 2 and i∈N (x) w(x,i) ≤ γU d. Also, i∈N (x) w(x, i) ≥ max{w(x, v)w(x, u)},
implying
w(x, v)w(x, u)
max{w(x, v)w(x, u)}2
P
P
≤
≤ max{w(x, v)w(x, u)}
i∈N (x) w(x, i)
i∈N (x) w(x, i)
P

P

Next we bound the size of the vertex cover formed by removing all leaves, compared to the
optimum.
Proof. (of Lemma 6.2) From [GS09, DDH09], given a tree T0 with root r0 , leaves l(T0 ), and parents
of the leaves p(T0 ), the greedy algorithm of taking p(T0 ) and iterating on T1 = T0 \ {l(T0 ) ∪ p(T0 )},
with r1 = r0 or r1 arbitrary if r0 ∈ p(T0 ), will give a minimum vertex cover of T0 . If T1 is a forest,
iterate on each tree of the forest, where r0 is the root of whichever tree it is contained in, and the
remaining trees are arbitrarily rooted. Assume that if Ti = ri for some i, then p(Ti ) = ∅.
Set T = T0 and r = r0 , and suppose T0 can be decomposed into T0 . . . Td as above. Therefore,
Sd
Sd−1
i=0 p(Ti ) is a minimum vertex cover, and VC is p(Td ) ∪ i=0 (p(Ti ) ∪ l(Ti+1 ))
By construction, all p(Ti ) and l(Tj ) are disjoint, and we claim that |p(Ti )| ≥ |l(Ti+1 )| for all i.
Assume Ti is a tree, and this will clearly still hold if Ti is a collection of disjoint trees. Each vertex
in l(Ti+1 ) was not a leaf in Ti and is now a leaf in Ti+1 . Further, ri ∈
/ l(Ti+1 ) because if ri ∈ Ti+1 ,
64

then ri+1 = ri . Therefore, each vertex in l(Ti+1 ) must have had its degree reduced by removing
l(Ti ) and p(Ti ). A vertex in l(Ti+1 ) cannot be connected to a vertex in l(Ti ) because then it would
be in p(Ti ). Consequently, it must be connected to some vertex in p(Ti ), and if |p(Ti )| < |l(Ti+1 )|,
then two vertices in l(Ti+1 ) must be connected to the same vertex in p(Ti ), creating a cycle in Ti ,
giving a contradiction. Thus
|VC| = p(Td ) +

d−1
X

d−1
X

i=0

i=0

(|p(Ti )| + |l(Ti+1 )|) ≤ p(Td ) +

65

2|p(Ti )| ≤ 2

d
X
i=0

|p(Ti )| = 2|MVC|

