Space- and Time-Efficient Algorithm for Maintaining
Dense Subgraphs on One-Pass Dynamic Streams∗
Sayan Bhattacharya†

Monika Henzinger‡

Danupon Nanongkai§

arXiv:1504.02268v3 [] 22 Sep 2015

Charalampos E. Tsourakakis¶

Abstract
While in many graph mining applications it is crucial to handle a stream of updates efficiently
in terms of both time and space, not much was known about achieving such type of algorithm.
In this paper we study this issue for a problem which lies at the core of many graph mining
applications called densest subgraph problem. We develop an algorithm that achieves time- and
space-efficiency for this problem simultaneously. It is one of the first of its kind for graph
problems to the best of our knowledge.
Given an input graph G = (V, E), the “density” of a subgraph induced by a subset of nodes
S ⊆ V is defined as |E(S)|/|S|, where E(S) denotes the set of edges in E with both endpoints
in S. In the densest subgraph problem, the goal is to find a subset of nodes that maximizes the
density of the corresponding induced subgraph.
For any ǫ > 0, we present a dynamic algorithm that, with high probability, maintains a (4+ǫ)approximate solution for the densest subgraph problem under a sequence of edge insertions and
deletions in an input graph with n nodes. The algorithm uses Õ(n) space, and has an amortized
update time of Õ(1) and a query time of Õ(1). Here, Õ hides a O(poly log1+ǫ n) term. The
approximation ratio can be improved to (2 + ǫ) at the cost of increasing the query time to Õ(n).
It can be extended to a (2 + ǫ)-approximation sublinear-time algorithm and a distributedstreaming algorithm. Our algorithm is the first streaming algorithm that can maintain the
densest subgraph in one pass. Prior to this, no algorithm could do so even in the special
case of an incremental stream and even when there is no time restriction. The previously best
algorithm in this setting required O(log n) passes [Bahmani, Kumar and Vassilvitskii, VLDB’12].
The space required by our algorithm is tight up to a polylogarithmic factor.

∗

A preliminary version of this paper appeared in the 47th ACM Symposium on Theory of Computing (STOC
2015).
†
The Institute of Mathematical Sciences, Chennai, India. Part of this work was done while the author was in
Faculty of Computer Science, University of Vienna, Austria.
‡
Faculty of Computer Science, University of Vienna, Austria. The research leading to these results has received
funding from the European Unions Seventh Framework Programme (FP7/2007-2013) under grant agreement 317532
and from the European Research Council under the European Union’s Seventh Framework Programme (FP7/20072013) / ERC Grant Agreement number 340506.
§
KTH Royal Institute of Technology, Sweden. Part of this work was done while the author was in Faculty of
Computer Science, University of Vienna, Austria.
¶
Harvard University, School of Engineering and Applied Sciences.

i

Contents
1 Introduction
1.1 Problem definition . . . . .
1.2 Our Results . . . . . . . . .
1.3 Previous work . . . . . . . .
1.4 Overview of our techniques
1.5 Roadmap . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

2 Notations and Preliminaries
2.1 Three basic properties . . . . .
2.2 (α, d, L)-decomposition . . . . .
2.3 Two results on ℓ0 -sampling and
2.4 Concentration bounds . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . .
uniform hashing
. . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

1
1
3
4
5
6

.
.
.
.

6
7
8
10
10

3 A Semi-Streaming Algorithm

10

4 A Dynamic Algorithm with Fast Update and Query Times
4.1 Dynamically maintaining an (α, d, L)-decomposition . . . . . . . . . . . . . . . . . .
4.1.1 A high level overview of the potential function based analysis . . . . . . . . .
4.1.2 Analyzing the subroutine RECOVER(). . . . . . . . . . . . . . . . . . . . . .

12
13
14
15

5 A Semi-Streaming Algorithm with Fast Update and Query times
5.1 An Overview of Our Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Main technical challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Maintaining the randomly sampled edges in Õ(1) update time . . . . . . . . . . . . .
5.2.1 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Proof of Theorem 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 A high level overview of our algorithm: Sparse and Dense Intervals . . . . . . . . . .
5.4 Algorithm for sparse intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Algorithm for dense intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Basic building block for proving Theorem 5.5 . . . . . . . . . . . . . . . . . .
5.5.2 Overview of our algorithm for Theorem 5.6 . . . . . . . . . . . . . . . . . . .
5.5.3 The subroutine Dynamic-stream for a dense time-interval [t0 , t1 ] . . . . . .
5.5.4 Data structures for implementing the procedure in Figure 4 . . . . . . . . . .
5.5.5 Implementing the procedure in Figure 4 during a dense time-interval [t0 , t1 ] .
5.5.6 The amortized update time of Dynamic-Stream during a dense time-interval
5.5.7 Proof of Lemma 5.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.8 Proof of Lemma 5.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17
17
18
20
21
22
23
24
25
26
26
27
30
30
31
33
35

6 Extension to Directed Graphs
6.1 Notations and Preliminaries . . . . . . . . . . . . . . . . . . . . .
6.2 (α, dS ′ , dT ′ , L)-Decomposition and Its Properties . . . . . . . . .
6.3 The Algorithm for Maintaining an (α, dS ′ , dT ′ , L)-Decomposition
6.4 Wrapping Up: Proof of Theorem 6.2 . . . . . . . . . . . . . . . .

37
37
39
41
44

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

7 Sublinear-Time Algorithm

44

8 Distributed Streams

45
ii

9 Open problems

46

iii

1

Introduction

In analyzing large-scale rapidly-changing graphs, it is crucial that algorithms must use small space
and adapt to the change quickly. This is the main subject of interest in at least two areas, namely
data streams and dynamic algorithms. In the context of graph problems, both areas are interested
in maintaining some graph property, such as connectivity or distances, for graphs undergoing a
stream of edge insertions and deletions. This is known as the (one-pass) dynamic semi-streaming
model in the data streams community, and as the fully-dynamic model in the dynamic algorithm
community.
The two areas have been actively studied since at least the early 80s (e.g. [17, 35]) and have
produced several sophisticated techniques for achieving time and space efficiency. In dynamic
algorithms, where the primary concern is time, the heavy use of amortized analysis has led to
several extremely fast algorithms that can process updates and answer queries in poly-logarithmic
amortized time. In data streams, where the primary concern is space, the heavy use of sampling
techniques to maintain small sketches has led to algorithms that require space significantly less than
the input size; in particular, for dynamic graph streams the result by Ahn, Guha, and McGregor
[1] has demonstrated the power of linear graph sketches in the dynamic model, and initiated an
extensive study of dynamic graph streams (e.g. [1–3, 26, 27]). Despite numerous successes in these
two areas, we are not aware of many results that combine techniques from both areas to achieve
time- and space-efficiency simultaneously in dynamic graph streams. A notable exception we are
aware of is the connectivity problem, where one can combine the space-efficient streaming algorithm
of Ahn et al. [2] with the fully-dynamic algorithm of Kapron et al. [28]1 .

1.1

Problem definition

In this paper, we study the densest subgraph problem in dynamic and streaming setting. Fix any
unweighted undirected input graph G = (V, E). The density of a subgraph induced by the set of
nodes H ⊆ V is defined as ρ(H) = |E(H)|/|H|, where E(H) = {(u, v) ∈ E : u, v ∈ H} is the set of
edges in the induced subgraph. The densest subgraph of G is the subgraph induced by a node set
H ⊆ V that maximizes ρ(H), and we denote the density of such a subgraph by ρ∗ (G) = max ρ(H).
H⊆V

For any γ ≥ 1 and η, we say that η is an γ-approximate value of ρ∗ (G) if ρ∗ (G)/γ ≤ η ≤ ρ∗ (G).
The (static) densest subgraph problem is to compute or approximate ρ∗ (G) and the corresponding
subgraph. Throughout the paper, we use n = |V | and m = |E| to denote the number of nodes and
edges in the input graph, respectively.
This problem and its variants have been intensively studied in practical areas as it is an important primitive in analyzing massive graphs. Its applications range from identifying dense communities in social networks (e.g. [13]), link spam detection (e.g. [18]) and finding stories and events (e.g.
[4]); for many more applications of this problem see, e.g., [6, 31, 42, 43]. Goldberg [20] was one of
the first to study this problem although the notion of graph density has been around much earlier
(e.g. [30, Chapter 4]). His algorithm can solve this problem in polynomial time by using O(log n)
flow computations. Later Gallo, Grigoriadis and Tarjan slightly improved the running time using
parametric maximum flow computation. These algorithms are, however, not very practical, and an
algorithm that is more popular in practice is an O(m)-time O(m)-space 2-approximation algorithm
of Charikar [9]. However, as mentioned earlier, graphs arising in modern applications are huge
and keep changing, and the earlier algorithms cannot handle edge insertions/deletions in the input
graph. Consider, for example, an application of detecting a dense community in social networks.
1

We thank Valerie King (private communication) for pointing out this fact.

1

Since people can make new friends as well as “unfriend” their old friends, the algorithm must be
able to process these updates efficiently. With this motivation, it is natural to consider a dynamic
version of this problem as defined below.
Our Model. We start with an empty graph G = (V, E) where E = ∅. Subsequently, at each
time-step, an adversary either inserts an edge into the graph, or deletes an already existing edge
from the graph. The set of nodes, on the other hand, remain unchanged. The goal is to maintain
a good approximation to the value of the densest subgraph while processing this sequence of edge
insertions/deletions. More formally, we want to design a data structure for the input graph G =
(V, E) that supports the following operations.
• Initialize(V ): Initialize the data structure with an empty graph G = (V, E) where E = ∅.
• Insert(u, v): Insert the edge (u, v), where u, v ∈ V , into the graph G.
• Delete(u, v): Delete an existing edge (u, v) ∈ E from the graph G.
• QueryValue: Return an estimate of the value of the maximum density ρ∗ (G) = maxS⊆V ρ(S).
If this estimate is always within a γ-factor of ρ∗ (G), for some γ ≥ 1, then we say that the
algorithm maintains a γ-approximation to the value of the densest subgraph. We want this
approximation factor to be a small constant.
The performance of a data structure is measured in term of four different metrics, as defined below.
• Space-complexity: This is given by the total space (in terms of bits) used by the data structure.
• Update-time: This is the time taken to handle an Insert or Delete operation.
• Query-time: This is the time taken to handle a QueryValue operation.
• Preprocessing-time: This is the time taken to handle the Initialize operation. Unless explicitly mentioned otherwise, in this paper the preprocessing time will always be Õ(n).
Comparison with the semi-streaming model. In the streaming algorithms literature, the
“semi-streaming model” for graph problems is defined as follows. We start with an empty graph of
n nodes. Subsequently, we have to process a “stream” of updates in the graph. For “insert-only”
streams, each update consist of inserting a new edge into the graph. For “dynamic” (or, “turnstile”)
streams, each update consists of either inserting a new edge into the graph or deleting an already
existing edge from the graph.
A “semi-streaming algorithm” can use only Õ(n) bits of space while processing a stream of
updates. In particular, the algorithm cannot store all the edges in the graph (which might require
Ω(n2 ) space). At the end of the stream, the algorithm has to output an (approximate) solution
to the problem concerned, which, in our case, happens to be the value of the densest subgraph.
The algorithm is allowed to make “multiple passes” over this stream. Typically, in the streaming
algorithms literature the focus is on the space complexity, and optimizing the update-time and the
query-time (which can be as large as Ω(n)) are of secondary importance.
Our goal. We want to design algorithms that maintain constant factor approximations to the
value of the densest subgraph in a dynamic setting, have very fast (polylogarithmic in n) update
and query times, and use very little (near-linear in n) space. In other words, we want single-pass
semi-streaming algorithms over dynamic streams with polylogarithmic update and query times.

2

Remark on the query operation. The QueryValue operation described above asks only for
an estimate of the value ρ∗ (G). This raises a natural question: Can we answer a more general
query that asks for a subset of nodes which constitute an approximate densest subgraph (in time
proportional to the number of nodes returned in response to the query)? The answer is yes. We
can easily extend all the algorithms presented in this paper so as to enable them with this new
feature (see the discussion after the proof of Corollary 2.7).

1.2

Our Results

Our main result is an efficient (4 + ǫ)-approximation algorithm for this problem (see Theorem 1.1).
To be more specific, we present a randomized algorithm that can process a stream of polynomially
many edge insertions/deletions starting from an empty graph using only Õ(n) space, and with high
probability, the algorithm maintains a (4 + ǫ)-approximation to the value of the densest subgraph.
The algorithm has Õ(1) amortized update-time and Õ(1) query-time.
For every integer t ≥ 0, let G(t) = (V, E (t) ) be the state of the input graph G = (V, E) just
after we have processed the first t updates (edge insertions/deletions) in the dynamic stream, and
define m(t) ← |E (t) |. Thus, we have m(0) = 0 and m(t) ≥ 0 for all t ≥ 1. We let Opt(t) = ρ∗ (G(t) )
denote the density of the densest subgraph in G(t) .
Notation. Throughout this paper, the notations Õ(.) and Θ̃(.) will hide poly(log n, 1/ǫ) factors
in the running times and space complexities of our algorithms, where ǫ ∈ (0, 1) is a small constant.
Theorem 1.1. Fix a small constant ǫ ∈ (0, 1), a constant λ > 1, and let T = ⌈nλ ⌉. We can
process the first T updates (edge insertions/deletions) in a dynamic stream using Õ(n) space, and
maintain a value Output(t) at each t ∈ [T ]. The algorithm gives the following guarantees with
high probability: We have Opt(t) /(4 + O(ǫ)) ≤ Output(t) ≤ Opt(t) for all t ∈ [T ]. Further, the
total amount of computation performed while processing the first T updates in the stream is Õ(T ).
Oblivious Adversary. We remark that Theorem 1.1 holds only when the sequence of edge
insertions/deletions in the input graph does not depend on the random bits used by our algorithm.
In other words, the “adversary”, who decides upon the sequence of edge insertions/deletions, is
“oblivious” to the random bits used in the algorithm. This is a standard assumption in the graph
streaming literature. For example, the paper by Ahn, Guha and McGregor [1] also requires this
assumption on the adversary. We prove Theorem 1.1 in Section 5. In addition, we obtain the
following results.
• A (2 + ǫ)-approximation one-pass dynamic semi-streaming algorithm: This follows
from the fact that with the same space, preprocessing time, and update time, and an additional
Õ(n) query time, our main algorithm can output a (2 + ǫ)-approximate solution. See Section 3.
• A (4 + ǫ)-approximation deterministic dynamic algorithm with Õ(1) update time. In
Section 4, we present a deterministic algorithm that maintains a (4 + ǫ)-approximation to the value
of the densest subgraph. This requires Õ(m + n) space, and Õ(1) update and query times.
• Extensions to directed graphs. In Section 6, we extend our result from Section 4 to directed graphs. Specifically, we present a deterministic dynamic algorithm that maintains a (8 + ǫ)approximation to the value of the densest subgraph of a directed graph. This requires Õ(m + n)
space, and Õ(1) update and query times.

3

• Sublinear-time algorithm: We show that Charikar’s linear-time linear-space algorithm [9]
can be improved further. In particular, if the graph is represented by an incident list (this is a
standard representation [10, 19]), our algorithm needs to read only Õ(n) edges in the graph (even if
the graph is dense) and requires Õ(n) time to output a (2+ǫ)-approximate solution. We also provide
a lower bound that matches this running time up to a poly-logarithmic factor. See Section 7.
• Distributed streaming algorithm: In the distributed streaming setting with k sites as defined in [11], we can compute a (2 + ǫ)-approximate solution with Õ(k + n) communication by
employing the algorithm of Cormode et al. [11]. See Section 8.

1.3

Previous work

To the best of our knowledge, our main algorithm is the first dynamic graph algorithm that requires
Õ(n) space and at the same time can quickly process each update and answer each query for
densest subgraph. Previously, there was no space-efficient algorithm known for this problem, even
when time efficiency is not a concern, and even for insert-only streams. In this insert-only model,
Bahmani, Kumar, and Vassilvitskii [6] provided a deterministic (2 + ǫ)-approximation O(n)-space
algorithm. Their algorithm needs O(log1+ǫ n) passes; i.e., it has to read through the sequence of
edge insertions O(log1+ǫ n) times. (Their algorithm was also extended to a MapReduce algorithm,
which was later improved by [5].) In Section 3, we improve this result of Bahmani et al. in two
respects: (a) We can process a dynamic stream of updates, and (b) we need only a single pass.
Further, the space usage of our algorithm from Section 3 matches the lower bound provided by [6,
Lemma 7] up to a polylogarithmic factor.
We note that while in some settings it is reasonable to compute the solution at the end of the
stream or even make multiple passes (e.g. when the graph is kept on an external memory), and
thus our and Bahmani et al’s (2 + ǫ)-approximation algorithms are sufficient in these settings, there
are many natural settings where the stream keeps changing, e.g. social networks where users keep
making new friends and disconnecting from old friends. In the latter case our main algorithm is
necessary since it can quickly prepare to answer the densest subgraph query after every update.
Another related result in the streaming setting is by Ahn et al. [2] which approximates the
fraction of some dense subgraphs such as a small clique in dynamic streams. This algorithm does
not solve the densest subgraph problem but might be useful for similar applications.
Not much was known about time-efficient algorithm for this problem even when space efficiency
is not a concern. One possibility is to adapt dynamic algorithms for the related problem called
dynamic arboricity. The arboricity of a graph G is α(G) = maxU ⊆V (G) |E(U )|/(|U |−1) where E(U )
is the set of edges of G that belong to the subgraph induced by U . Observe that ρ∗ (G) ≤ α(G) ≤
2ρ∗ (G). Thus, a γ-approximation algorithm for the arboricity problem will be a (2γ)-approximation
algorithm for densest subgraph. In particular, we can use the 4-approximation algorithm of Brodal
and Fagerberg [7] to maintain an 8-approximate solution to the densest subgraph problem in Õ(1)
amortized update time. (With a little more thought, one can in fact improve the approximation
ratio to 6.)
In a work that appeared at about the same time as the preliminary version of this paper,
Epasto et al. [14] presented a (2 + ǫ)-approximation algorithm for densest subgraph which can
handle arbitrary edge insertions and random edge deletions. After the preliminary version of our
paper appeared, Esfandiari et al. [16] and McGregor et al. [33] presented semi-streaming algorithms
for densest subgraph that give (1 + ǫ)-approximation and require Õ(n) space. The same result was
obtained independently by Mitzenmacher et al. [34]. These improve the approximation ratio of our
(2 + ǫ)-approximation semi-streaming algorithm. Like our (2 + ǫ)-approximation algorithm, their
algorithms have an update-time of Õ(1), but the query-time can be as large as Ω̃(n).
4

1.4

Overview of our techniques

An intuitive way to combine techniques from data streams and dynamic algorithms for any problem
is to run the dynamic algorithm using the sketch produced by the streaming algorithm as an input.
This idea does not work straightforwardly. The first obvious issue is that the streaming algorithm
might take excessively long time to maintain its sketch and the dynamic algorithm might require
an excessively large additional space. A more subtle issue is that the sketch might need to be
processed in a specific way to recover a solution, and the dynamic algorithm might not be able
to facilitate this. As an extreme example, imagine that the sketch for our problem is not even a
graph; in this case, we cannot even feed this sketch to a dynamic algorithm as an input.
The key idea that allows us to get around this difficulty is to develop streaming and dynamic
algorithms based on the same structure called (α, d, L)-decomposition. This structure is an extension of a concept called d-core, which was studied in graph theory since at least the 60s (e.g.,
[15, 32, 41]) and has played an important role in the studies of the densest subgraph problem (e.g.,
[6, 40]). The d-core of a graph is its (unique) largest induced subgraph with every node having
degree at least d. It can be computed by repeatedly removing nodes of degree less than d from
the graph, and can be used to 2-approximate the densest subgraph. Our (α, d, L)-decomposition
with parameter α ≥ 1 is an approximate version of this process where we repeatedly remove nodes
of degree “approximately” less than d: in this decomposition we must remove all nodes of degree
less than d and are allowed to remove some nodes of degree between d and αd. We will repeat this
process for L iterations. Note that the (α, d, L)-decomposition of a graph is not unique. However,
for L = O(log1+ǫ n), an (α, d, L)-decomposition can be use to 2α(1 + ǫ)2 -approximate the densest
subgraph. We explain this concept in detail in Section 2.2.
We show that this concept can be used to obtain an approximate solution to the densest
subgraph problem and leads to both a streaming algorithm with a small sketch and a dynamic
algorithm with small amortized update time. In particular, it is intuitive that to check if a node
has degree approximately d, it suffices to sample every edge with probability roughly 1/d. The
value of d that we are interested in is approximately ρ∗ (G), which can be shown to be roughly the
same as the average degree of the graph. Using this fact, it follows almost immediately that we
only have to sample Õ(n) edges. Thus, to repeatedly remove nodes for L iterations, we will need
to sample Õ(Ln) = Õ(n) edges (we need to sample a new set of edges in every iteration to avoid
dependencies).
We turn the (α, d, L)-decomposition concept into a dynamic algorithm by dynamically maintaining the sets of nodes removed in each of the L iterations, called levels. Since the (α, d, L)decomposition gives us a choice whether to keep or remove each node of degree between d and
αd, we can save time needed to maintain this decomposition by moving nodes between levels only
when it is necessary. If we allow α to be large enough, nodes will not be moved often and we can
obtain a small amortized update time; in particular, it can be shown that the amortized update
time is Õ(1) if α ≥ 2 + ǫ. In analyzing an amortized time, it is usually tricky to come up with the
right potential function that can keep track of the cost of moving nodes between levels, which is
not frequent but expensive. In case of our algorithm, we have to define two potential functions for
our amortized analysis, one on nodes and one on edges. (For intuition, we provide an analysis for
the simpler case where we run this dynamic algorithm directly on the input graph in Section 4.)
Our goal is to run the dynamic algorithm on top of the sketch maintained by our streaming
algorithm in order to maintain the (α, d, L)-decomposition. To do this, there are a few issues we
have to deal with that makes the analysis rather complicated: In the sketch we maintain L sets of
sampled edges, and for each of the L iterations we use different such sets to determine which nodes
to remove. This causes the potential functions and its analysis to be even more complicated since
5

whether a node should be moved from one level to another depends on its degree in one set, but
the cost of moving such node depends on its degree in other sets as well. The analysis, however,
goes through (intuitively because all sets are sampled from the same graph and so their degree
distributions are close enough). See Section 5 for further details.

1.5

Roadmap

The rest of the paper is organized as follows.
• We define the preliminary concepts and notations in Section 2.
• In Section 3, we present an algorithm that returns a (2 + ǫ)-approximation to the value of the
densest subgraph. The algorithm processes a stream of edge insertions/deletions using only
Õ(n) bits of space, and at the end of the stream returns an estimate of ρ∗ (G) in Õ(n) time.
The output of the algorithm is correct with high probability.
• In Section 4, we present a deterministic algorithm that maintains a (4 + ǫ)-approximation to
the value of the densest subgraph in Õ(m + n) space. It has Õ(1) update and query times.
• We present our main result in Section 5. Specifically, combining the techniques from Sections 3
and 4, we design an algorithm that maintains a (4 + ǫ)-approximation to the value of the
densest subgraph with high probability, and requires only Õ(n) space and Õ(1) update time.
• In Section 6, we extend the result from Section 4 to directed graphs. Specifically, in a directed
graph, we present a deterministic algorithm that maintains an (8 + ǫ)-approximation to the
value of the densest subgraph using Õ(m + n) space. It has Õ(1) update and query times.
• In Sections 7 and 8 we present simple extensions of our result from Section 3, giving sublinear
time and distributed-streaming algorithms for densest subgraph.

2

Notations and Preliminaries

We start by defining some notations that will be used throughout the rest of the paper. We
denote the input graph by G = (V, E). It has n = |V | nodes and m = |E| edges. Let Nv =
{u ∈ V : (u, v) ∈ E} and Dv = |Nv | respectively denote the set of neighbors and the degree of a
node v ∈ V . Consider any subset of nodes S ⊆ V . Let E(S) = {(u, v) ∈ E : u, v ∈ S} denote
the set of edges with both endpoints in S, and let G(S) = (V, E(S)) denote the subgraph of G
induced by the nodes in S. Further, given any subset of edges E ′ ⊆ E and any node u ∈ V ,
define Nu (S, E ′ ) = {v ∈ Nu ∩ S : (u, v) ∈ E ′ } and Du (S, E ′ ) = |Nu (S, E ′ )|. In other words,
Nu (S, E ′ ) is the subset of nodes in S that are neighbors of u in the subgraph induced by the edges
in E ′ , whereas Du (S, E ′ ) denotes the degree of u among the nodes in S in the same subgraph.
For simplicity, we write Nu (S) and Du (S) instead of Nu (S, E) and Du (S, E). If the set of nodes
S ⊆ VP
is nonempty, then its density and average-degree are defined as ρ(S) = |E(S)|/|S| and
δ(S) = v∈S Dv (S)/|S| respectively. Throughout the paper, the symbol Õ(.) will be used to hide
poly(log n, 1/ǫ) factors in the running times of our algorithms, where ǫ > 0 is some arbitrary small
constant (the approximation guarantee will depend on ǫ). Finally, for any positive integer k, we
will use the symbol [k] to denote the set {1, . . . , k}.
This paper deals with the “Densest Subgraph Problem”, which is about finding a subset of
nodes of maximum density. Specifically, we want to find a subset of nodes S ⊆ V in the input
graph G = (V, E) that maximizes ρ(S). Further, a subset S ⊆ V is called a γ-approximate densest
6

subgraph, for γ ≥ 1, iff γ · ρ(S) ≥ maxS ′ ⊆V ρ(S ′ ). We will consider the densest subgraph problem
in a dynamic setting. For a detailed description of our model, see Section 1.1. The main result of
this paper is summarized below.
Theorem 2.1. There is a dynamic data structure for the densest subgraph problem that requires
Õ(n) bits of space, has an amortized update time of Õ(1), a query time of O(1), and with high
probability maintains a (4 + ǫ)-approximation to the value of the densest subgraph.
It follows that Theorem 2.1 gives a single-pass semi-streaming algorithm over dynamic streams
for the approximate densest subgraph problem. And, unlike most other semi-streaming algorithms,
Theorem 2.1 gives very fast update and query times.

2.1

Three basic properties

We now state three basic lemmas that will be used throughout the rest of the paper. The first
lemma shows that the average degree of a set of nodes is twice its density.
Lemma 2.2. For all S ⊆ V , we have δ(S) = 2 · ρ(S).
P
Proof. We have δ(S) = v∈S Dv (S)/|S| = 2 · |E(S)|/|S| = 2 · ρ(S). The second equality holds
since every edge is incident upon two nodes.
The second lemma gives simple upper and lower bounds on the maximum density of a subgraph.
Lemma 2.3. Let d∗ = maxS⊆V ρ(S) be the maximum density of any subgraph in G. Then m/n ≤
d∗ < n.
Proof. Clearly, we have d∗ ≥ ρ(V ) = |E|/|V | = m/n. On the other hand, consider any subset
of nodes S ′ ⊆ V . We have ρ(S ′ ) = |E(S ′ )|/|S ′ | < n|S ′ |/|S ′ | = n. The inequality holds since the
maximum degree of a node is (n − 1), and hence the subgraph induced by the nodes in S ′ can have
at most n|S ′ | edges. Thus, we get: d∗ = maxS ′ ⊆V ρ(S ′ ) < n.
The final lemma will also be very helpful in analyzing our algorithm in later sections.
Lemma 2.4. Let S ∗ ⊆ V be a subset of nodes with maximum density, i.e., ρ(S ∗ ) ≥ ρ(S) for all
S ⊆ V . Then Dv (S ∗ ) ≥ ρ(S ∗ ) for all v ∈ S ∗ . Thus, the degree of each node in G(S ∗ ) is at least
the density of S ∗ .
Proof. Suppose that there is a node v ∈ S ∗ with DS ∗ (v) < ρ(S ∗ ). Define the set S ′ ← S ∗ \ {v}.
We derive the following bound on the average degree in S ′ .
P
ø
u∈S ′ D (u)
′
δ(S ) =
|S ′ |
P
u∈S ∗ DS ∗ (u) − 2 · DS ∗ (v)
=
|S ∗ | − 1
δ(S ∗ ) · |S ∗ | − 2 · DS ∗ (v)
=
|S ∗ | − 1
∗
δ(S ) · |S ∗ | − δ(S ∗ )
>
(since by assumption DS ∗ (v) < ρ(S ∗ ) = δ(S ∗ )/2)
|S ∗ | − 1
= δ(S ∗ )
Since δ(S ′ ) > δ(S ∗ ), we infer that ρ(S ′ ) > ρ(S ∗ ). But this contradicts the assumption that the
subset of nodes S ∗ has maximum density. Thus, we conclude that DS ∗ (v) ≥ ρ(S ∗ ) for every node
v ∈ S∗.
7

2.2

(α, d, L)-decomposition

Our algorithms will use the concept of an “(α, d, L)-decomposition”, as defined below. To give
some intuitions behind Definition 2.5, suppose that we start by setting Z1 ← V . Next, suppose
that we have already constructed the subsets Z1 ⊇ · · · ⊇ Zi for some positive integer i < L. While
constructing the next subset Zi+1 , we ensure that the following two conditions are satisfied.
• All the nodes v ∈ Zi with Dv (Zi ) > αd must be included in Zi+1 .
• All the nodes v ∈ Zi with Dv (Zi ) < d must be excluded from Zi+1 .
Using this iterative procedure, we can build an (α, d, L)-decomposition.
Definition 2.5. Fix any α ≥ 1, d ≥ 0, and any positive integer L. Consider a family of subsets
Z1 ⊇ · · · ⊇ ZL . The tuple (Z1 , . . . , ZL ) is an (α, d, L)-decomposition of the input graph G =
(V, E) iff Z1 = V and, for every i ∈ [L − 1], we have Zi+1 ⊇ {v ∈ Zi : Dv (Zi ) > αd} and Zi+1 ∩
{v ∈ Zi : Dv (Zi ) < d} = ∅.
Given an (α, d, L)-decomposition (Z1 , . . . , ZL ), we define Vi = Zi \ Zi+1 for all i ∈ [L − 1], and
Vi = Zi for i = L. We say that the nodes in Vi constitute the ith level of this decomposition. We
also denote the level of a node v ∈ V by ℓ(v). Thus, we have ℓ(v) = i whenever v ∈ Vi .
The following theorem and its immediate corollary will be of crucial importance. Roughly
speaking, they state that we can use the (α, d, L)-decomposition to 2α(1 + ǫ)2 -approximate the
densest subgraph by trying different values of d in powers of (1 + ǫ).
Theorem 2.6. Fix any α ≥ 1, d ≥ 0, ǫ ∈ (0, 1), L = 2 + ⌈log(1+ǫ) n⌉. Let d∗ = maxS⊆V ρ(S) be the
maximum density of any subgraph in G = (V, E), and let (Z1 , . . . , ZL ) be an (α, d, L)-decomposition
of G = (V, E). Then we have:
1. If d > 2(1 + ǫ)d∗ , then ZL = ∅.
2. Else if d < d∗ /α, then ZL 6= ∅ and there is an index j ∈ {1, . . . , L − 1} such that ρ(Zj ) ≥
d/(2(1 + ǫ)).
Proof.
1. Suppose that d > 2(1 + ǫ)d∗ . Consider any level i ∈ [L − 1], and note that δ(Zi ) = 2 · ρ(Zi ) ≤
2 · maxS⊆V ρ(S) = 2d∗ < d/(1 + ǫ). It follows that the number of nodes v in G(Zi ) with
degree Dv (Zi ) ≥ d is less than |Zi |/(1 + ǫ), as otherwise δ(Zi ) ≥ d/(1 + ǫ). Let us define the
set Ci = {v ∈ Zi : Dv (Zi ) < d}. We have |Zi \ Ci | ≤ |Zi |/(1 + ǫ). Now, from Definition 2.5 we
have Zi+1 ∩ Ci = ∅, which, in turn, implies that |Zi+1 | ≤ |Zi \ Ci | ≤ |Zi |/(1 + ǫ). Thus, for all
i ∈ [L − 1], we have |Zi+1 | ≤ |Zi |/(1 + ǫ). Multiplying all these inequalities, for i = 1 to L − 1,
we conclude that |ZL | ≤ |Z1 |/(1 + ǫ)L−1 . Since |Z1 | = |V | = n and L = 2 + ⌈log(1+ǫ) n⌉, we
get |ZL | ≤ n/(1 + ǫ)(1+log(1+ǫ) n) < 1. This can happen only if ZL = ∅.
2. Suppose that d < d∗ /α, and let S ∗ ⊆ V be a subset of nodes with highest density, i.e.,
ρ(S ∗ ) = d∗ . We will show that S ∗ ⊆ Zi for all i ∈ {1, . . . , L}. This will imply that ZL 6= ∅.
Clearly, we have S ∗ ⊆ V = Z1 . By induction hypothesis, assume that S ∗ ⊆ Zi for some
i ∈ [L − 1]. We show that S ∗ ⊆ Zi+1 . By Lemma 2.4, for every node v ∈ S ∗ , we have
Dv (Zi ) ≥ Dv (S ∗ ) ≥ ρ(S ∗ ) = d∗ > αd. Hence, from Definition 2.5, we get v ∈ Zi+1 for all
v ∈ S ∗ . This implies that S ∗ ⊆ Zi+1 .
8

Next, we will show that if d < d∗ /α, then there is an index j ∈ {1, . . . , L − 1} such that
ρ(Zj ) ≥ d/(2(1 + ǫ)). For the sake of contradiction, suppose that this is not the case. Then
we have d < d∗ /α and δ(Zi ) = 2 · ρ(Zi ) < d/(1 + ǫ) for every i ∈ {1, . . . , L − 1}. Then,
applying an argument similar to case (1), we conclude that |Zi+1 | ≤ |Zi |/(1 + ǫ) for every
i ∈ {1, . . . , L − 1}, which implies that ZL = ∅. Thus, we arrive at a contradiction.
Corollary 2.7. Fix α, ǫ, L, d∗ as in Theorem 2.6. Let π, σ > 0 be any two numbers satisfying
α · π < d∗ < σ/(2(1 + ǫ)). Fix any integer K ≥ 2 + ⌈log(1+ǫ) (σ/π)⌉. Discretize the range [π, σ] into
powers of (1+ǫ), by defining dk = (1+ǫ)k−1 ·π for every k ∈ [K]. Next, for every k ∈ [K], construct
an (α, dk , L)-decomposition (Z1 (k), . . . , ZL (k)) of G = (V, E). Let k ′ = max{k ∈ [K] : ZL (k) 6= ∅}.
Then we have the following guarantees:
1. d∗ /(α(1 + ǫ)) ≤ dk′ ≤ 2(1 + ǫ)2 · d∗ .
2. There exists an index j ′ ∈ {1, . . . , L − 1} such that ρ(Zj ′ (k′ )) ≥ dk′ /(2(1 + ǫ)).
Proof.
1. Note that π < d∗ /α and σ > 2d∗ (1 + ǫ). Furthermore, we have d1 < π and dK ≥ (1 + ǫ)σ.
This implies that d1 < d∗ /α and dK > 2d∗ (1 + ǫ)2 . Next, note that successive dk values differ
from each other by a factor of (1 + ǫ). Accordingly, there exists some index k ∈ [K] for which
d∗ /(α(1+ǫ)) ≤ dk ≤ 2(1+ǫ)2 ·d∗ . In other words, the set Q = {k ∈ [K] : d∗ /(α(1+ǫ)) ≤ dk ≤
2(1 + ǫ)2 · d∗ } is nonempty. Let k1 = mink∈Q {k} and k2 = maxk∈Q {k} respectively denote
the minimum and maximum indices in the set Q. Observe that the set Q is “contiguous”,
i.e., Q = {k1 , k1 + 1, . . . , k2 }. Since the dk values are discretized in powers of (1 + ǫ), we have
k1 < d∗ /α and k2 > 2d∗ (1 + ǫ). Hence, by Theorem 2.6, we have ZL (k1 ) 6= ∅, and ZL (k) = ∅
for all k ≥ k2 . It follows that the index k′ must satisfy the inequality k1 ≤ k′ ≤ k2 , which
means that k′ ∈ Q. Thus, we have d∗ /(α(1 + ǫ) ≤ k′ ≤ 2(1 + ǫ)2 d∗ .
2. Suppose that the claim is false. Then we have ZL (k′ ) 6= ∅ and δ(Zi (k′ )) = 2 · ρ(Zi (k′ )) <
dk′ /(1+ǫ) for every i ∈ {1, . . . , L−1}. Then, applying an argument similar to the proof of case
(1) in Theorem 2.6, we conclude that |Zi+1 (k′ )| ≤ |Zi (k′ )|/(1 + ǫ) for every i ∈ {1, . . . , L − 1},
which implies that ZL (k′ ) = ∅. Thus, we arrive at a contradiction.
We will use the above corollary as follows. Lemma 2.3 states that m/n ≤ d∗ < n. Thus, in
Corollary 2.7, we can choose the values of π, σ and K in such a way which ensures that K = Θ̃(1).
Hence, to maintain a 2α(1 + ǫ)3 = (2α + Θ(ǫ))-approximation of the maximum density, it suffices to
maintain K = Θ̃(1) many (α, d, L)-decompositions and to keep track of the maximum d for which
the topmost level (i.e., the node set VL ) of the decomposition is nonempty. This gives a query
time of O(1). In addition, if we want to answer a more general query which asks us to output a
subgraph of approximate maximum density, then we simply keep track of the densities of all the
node-induced subgraphs of the form Zi (k), where i ∈ [L − 1], k ∈ [K], and output the one among
them with maximum density. Since there are only K = Θ̃(1) many decompositions to consider, and
since each such decomposition has L = Θ̃(1) levels, this can be done by incurring an additional cost
of no more than Θ(KL) = Θ̃(1) in the update time. It turns our that this simple extension applies
to all the dynamic and streaming algorithms presented in the paper. Accordingly, for simplicity of
exposition, from now on we only focus on the simpler query which asks for an estimate of the value
of the densest subgraph (and not the subgraph itself).
9

2.3

Two results on ℓ0 -sampling and uniform hashing

We now state a well known result on ℓ0 -sampling in the streaming setting. All the streaming
algorithms in this paper will use this result.
Lemma 2.8 (ℓ0 -sampler [24]). We can process a dynamic stream of O(poly n) updates in the graph
G = (V, E) in Õ(1) space, and with high probability, at each step we can maintain a simple random
sample from the set E. The algorithm takes Õ(1) time to handle each update in the stream.
The next lemma deals with uniform hashing in constant time and optimal space. We will use
this lemma in Section 5.2.

Lemma 2.9. [37]. Let E ∗ = [n]
be the set of all possible unordered pairs of nodes in V .
2
Consider any two integers w, q ≥ 1. We can construct a w-wise independent uniform hash function
h : E ∗ → [q] using O(w poly(log w, log q, log n)) bits of space. Given any e ∈ E ∗ , the hash value
h(e) can be evaluated in O(1) time.

2.4

Concentration bounds

We will use the following concentration bounds throughout the rest of this paper.
Theorem 2.10. (Chernoff bound-I) Consider a collection of mutuallyPindependent random variables {X1 , . . . , Xt } such that Xi ∈ [0, 1] for all i ∈ {1, . . . , t}. Let X = ti=1 Xi be the sum of these
2
random variables. Then we have Pr[X > (1 + ǫ)µ] ≤ e−ǫ µ/3 whenever E[X] ≤ µ.
Theorem 2.11. (Chernoff bound-II) Consider a set of mutually independent
random variables
P
{X1 , . . . , Xt } such that Xi ∈ [0, 1] for all i ∈ {1, . . . , t}. Let X = ti=1 Xi be the sum of these
2
random variables. Then we have Pr[X < (1 − ǫ)µ] ≤ e−ǫ µ/2 whenever E[X] ≥ µ.
Definition 2.12. (Negative association) A set of random variables {X1 , . . . , Xt } are negatively
associated iff for all disjoint subsets I, J ⊆ {1, . . . , t} and all non-decreasing functions f and g, we
have E[f (Xi , i ∈ I) · g(Xj , j ∈ J)] ≤ E[f (Xi , i ∈ I)] · E[g(Xj , j ∈ J)].
Theorem 2.13. (Chernoff bound with negative dependence) The Chernoff bounds, as stated in
Theorems 2.10 and 2.11, hold even if the random variables {X1 , . . . , Xt } are negatively associated.

3

A Semi-Streaming Algorithm

In this section, we present a single-pass semi-streaming algorithm for the densest subgraph problem.
The algorithm requires only Õ(n) bits of space, and at the end of the stream outputs a (2 + ǫ)approximation to the value of the densest subgraph with high probability. On the negative side,
its update time can be as large as Ω(n). Our result in this section is stated in the theorem below.
Theorem 3.1. In a single pass, we can process a dynamic stream of updates in the graph G in Õ(n)
space. With high probability, we can return a (2 + O(ǫ))-approximation of the maximum density
d∗ = maxS⊆V ρ(S) at the end of the stream.
We devote the rest of this section to the proof of Theorem 3.1. Throughout this section,
we fix a small constant ǫ ∈ (0, 1/2) and a sufficiently large constant c > 1. Moreover, we set
α ← (1 + ǫ)/(1 − ǫ), L ← 2 + ⌈log(1+ǫ) n⌉.
First, we show that we can construct a (α, d, L)-decomposition by sampling Õ(n) edges.
10

Lemma 3.2. Fix an integer d > 0, and let S be a collection of cm(L − 1) log n/d mutually independent random samples (each consisting of one edge) from the edge set E of the input graph
G = (V, E). With high probability we can construct from S an (α, d, L)-decomposition (Z1 , . . . , ZL )
of G, using only Õ((n + m/d)) bits of space.
Proof. We partition the samples in S evenly among (L − 1) groups {Si } , i ∈ [L − 1]. Thus, each
Si is a collection of cm log n/d mutually independent random samples from the edge set E, and,
furthermore, the collections {Si } , i ∈ [L − 1], themselves are mutually independent.
Consider any index i ∈ {1, . . . , L − 1}. Note that an edge (u, v) ∈ E can appear multiple times
in the collection of samples Si . We will slightly abuse the notation introduced in the beginning of
Section 2, and let Dv (V ′ , Si ) denote the degree of a node v ∈ V ′ ⊆ V in the multigraph induced by
the node set V ′ and the samples in Si . With this notation in hand, our algorithm works as follows.
• Set Z1 ← V .
• For i = 1 to (L − 1): Set Zi+1 ← {v ∈ Zi : Dv (Zi , Si ) ≥ (1 − ǫ)αc log n}.
To analyze the correctness of the algorithm, define the (random) sets Ai = {v ∈ Zi : Dv (Zi , E) >
αd} and Bi = {v ∈ Zi : Dv (Zi , E) < d} for all i ∈ [L − 1]. Note that for all i ∈ [L − 1], the
random sets Zi , Ai , Bi are completely determined by the outcomes of the samples in {Sj } , j < i.
In particular, the samples in Si are chosen independently of the sets Zi , Ai , Bi . Let Ei be the event
that (a) Zi+1 ⊇ Ai and (b) Zi+1 ∩ Bi =T∅. By Definition 2.5, the output (Z1 , . . . , ZL ) is a valid
L−1
(α, d, L)-decomposition of G iff the event i=1
Ei occurs. Consider any i ∈ [L − 1]. Below, we show
that the event Ei occurs with high probability. The lemma follows by taking a union bound over
all i ∈ [L − 1].
Fix any instantiation of the random set Zi . Condition on this event, and note that this event
completely determines the sets Ai , Bi . Consider any node v ∈ Ai . Let Xv,i (j) ∈ {0, 1} be an
indicator random variable for the event that the j th sample in Si is of the form (u, v), with u ∈
Nv (Zi ). Note that the random variables {Xv,i (j)}, j, are mutually independent. Furthermore, we
have E[Xv,i (j)|Zi ] = Dv (Zi )/m > αd/m for all j. Since
P there are cm log n/d such samples in Si ,
by linearity of expectation we get: E[Dv (Zi , Si )|Zi ] = j E[Xv,i (j)|Zi ] > (cm log n/d) · (αd/m) =
αc log n. The node v is included in Zi+1 iff Dv (Zi , Si ) ≥ (1 − ǫ)αc log n, and this event, in turn,
occurs with high probability (by Chernoff bound). Taking a union bound over all nodes v ∈ Ai ,
we conclude that Pr[Zi+1 ⊇ Ai | Zi ] ≥ 1 − 1/(poly n). Using a similar line of reasoning, we get
that Pr[Zi+1 ∩ Bi = ∅ | Zi ] ≥ 1 − 1/(poly n). Invoking a union bound over these two events, we get
Pr[Ei | Zi ] ≥ 1 − 1/(poly n). Since this holds for all possible instantiations of Zi , the event Ei itself
occurs with high probability.
The space requirement of the algorithm, ignoring poly log factors, is proportional to the number
of samples in S (which is cm(L − 1) log n/d) plus the number of nodes in V (which is n). Since c is a
constant and since L = Õ(1), we derive that the total space requirement is O((n + m/d) poly log n).
Now, to turn Lemma 3.2 into a streaming algorithm, we simply have to invoke Lemma 2.8 which
follows from a well-known result about ℓ0 -sampling in the streaming model [24], and a simple (but
important) observation in Lemma 2.3.
Proof of Theorem 3.1. Define λ∗ = 2α · (cn(L − 1) log n) and K ∗ = 2 + ⌈log(1+ǫ) (8αn2 )⌉. While
processing the stream of edge insertions/deletions, we simultaneously run λ∗ K ∗ mutually independent copies of the ℓ0 -sampler as per Lemma 2.8. Furthermore, we maintain a counter to keep track
of the number of edges in the graph. Initially, the counter is set to zero. After each edge insertion
11

(resp. deletion), the counter is incremented (resp. decremented) by one. Thus, at the end of the
stream, we get λ∗ K ∗ mutually independent uniform random samples from the edge set E, and a
correct estimate of the number of edges in the graph (which is given by m = |E|). All these steps
can be implemented in Θ̃(λ∗ K ∗ ) = Θ̃(n) space. Note that if m = 0, then clearly the maximum

density of a subgraph is also zero. Thus, for the rest of the proof, we assume that 1 ≤ m ≤ n2 .
Next, at the end of the stream, we define π = m/(2αn) and σ = 2(1 + ǫ)n. By Lemma 2.3,
we have α · π < d∗ < σ/(2(1 + ǫ)). Thus, the values of π and σ satisfies the condition required
by Corollary 2.7. Hence, following Corollary 2.7, we set K = 2 + ⌈log(1+ǫ) (σ/π)⌉, and discretize
the range [π, σ] in powers of (1 + ǫ) by defining dk = (1 + ǫ)k−1 · π for every integer k ∈ [K].
Furthermore, we define λk = cm(L − 1) log n/dk for all k ∈ [K]. Our goal is toPconstruct an
(α, dk , L)-decomposition of G for every k ∈ [K]. By Lemma 3.2, for this we need K
k=1 λk many
mutually independent random samples from E. But note that:
λk ≥ λ1 = cm(L − 1) log n/d1 = cm(L − 1) log n/π = 2α · (c(L − 1)n log n) = λ∗

for all k ∈ [K].

Next, since π = m/(2αn), σ = 2(1 + ǫ)n and m ≥ 1, we also have K ∗ = 2 + ⌈log(1+ǫ) (8αn2 )⌉ ≥
2 + ⌈log(1+ǫ) (σ/π)⌉ = K. To summarize, we infer the following guarantee.
K
X
k=1

λK ≤ λ∗ K ∗ .

In other words, while processing the stream of edge insertions/deletions, we have collected sufficiently many mutually independent random samples from E so as to construct an (α, dk , L)decomposition for every integer k ∈ [K]. We can now get a (2α + Θ(ǫ)) = (2 + Θ(ǫ))-approximation
to the value of the densest subgraph by invoking Corollary 2.7.
Remark on the update and query times. The semi-streaming algorithm presented in this
section runs Θ̃(n) mutually independent ℓ0 -samplers as per Lemma 2.8. Thus, when an edge is
inserted into (resp. deleted from) the graph, the algorithm has to update each of these ℓ0 -samplers.
This requires an update time of Θ̃(n). Finally, to answer a query about the maximum density,
we have to first construct Θ̃(1) many (α, d, L) decompositions (for different values of d) from the
sampled edges maintained by the ℓ0 samplers, and then invoke Corollary 2.7. Thus, the query time
is also Θ̃(n).

4

A Dynamic Algorithm with Fast Update and Query Times

The algorithm in Section 3 maintains a (2 + ǫ)-approximation to the value of the densest subgraph
and requires only Õ(n) space, but its update and query times can be as large as Ω(n). In this
section, we present an algorithm with Õ(1) update and query times. This algorithm, however, has
to store all the edges in the graph and hence has a space requirement of Θ̃(m + n). Furthermore,
this algorithm maintains an approximation guarantee of (4 + ǫ).
Throughout this section, we set π = 1/(4n), σ = 4n, L = 2 + ⌈log(1+ǫ) n⌉, and α = 2 + 3ǫ, where
ǫ ∈ (0, 1) is some small constant. Note that α · π < d∗ < σ/(2(1 + ǫ)), where d∗ is the optimal
density in the input graph. As in Corollary 2.7, we discretize the range [π, σ] in powers of (1 + ǫ)
by defining the values {dk }, k ∈ [K], by setting K = 2 + ⌈log(1+ǫ) (σ/π)⌉.
We show in Section 4.1 how to maintain an (α, dk , L)-decomposition of G for each k ∈ [K]
in O(L/ǫ) = O(log n/ǫ2 ) amortized update time and Θ(m + n) space (see Theorem 4.2). Since
K = O(log n/ǫ), the total update time for all the K decompositions is O(K log n/ǫ2 ) = Õ(1) and
12

the total space requirement is also O(K · (m + n)) = Õ(m + n). By Corollary 2.7, this gives a
2α(1 + ǫ)2 = 4 + O(ǫ)-approximation to the optimal density in G, for sufficiently small ǫ. To answer
a query about the value of the densest subgraph, the algorithm needs to keep track of the index
k′ as defined in Corollary 2.7. Since there are O(K) = Õ(1) decompositions to deal with, the time
taken for this operation can be subsumed within the Õ(1) update time. This gives us a query time
of O(1). We thus get the main result of this section, which is summarized below.
Theorem 4.1. There is a deterministic dynamic algorithm that maintains a (4+O(ǫ))-approximation
to the value of the densest subgraph. The algorithm requires Õ(m+n) space, has an amortized update
time of Õ(1) and a query time of O(1).

4.1

Dynamically maintaining an (α, d, L)-decomposition

We present a deterministic data structure that is initially given α, d, L, and a graph G = (V, E) with
|V | = n, E = ∅. The data structure maintains an (α, d, L)-decomposition of the graph G = (V, E)
at each time-step, and supports the following operations:
• Insert(u, v): Insert the edge (u, v) into the graph.
• Delete (u, v): Delete the edge (u, v) from the graph.
Theorem 4.2 summarizes our result. We devote the rest of Section 4.1 to its proof.
Theorem 4.2. For every polynomially bounded α ≥ 2 + 3ǫ, we can deterministically maintain an
(α, d, L)-decomposition of G = (V, E). Starting from an empty graph, our data structure handles a
sequence of t update operations (edge insertions/deletions) in total time O(tL/ǫ). Thus, we get an
amortized update time of O(L/ǫ). The space complexity of the data structure at a given time-step
is O(n + m), where m = |E| denotes the number of edges in the input graph at that time-step.
Data Structures.

We use the following data structures.

1. Every node v ∈ V maintains L lists Friendsi [v], for i ∈ {1, . . . , L}. For i < ℓ(v), the list
Friendsi [v] consists of the neighbors of v that are at level i (given by the set Nv (Vi )). For
i = ℓ(v), the set Friendsi [v] consists of the neighbors of v that are at level i or above (given
by the set Nv (Zi )). For i > ℓ(v), the list Friendsi [v] is empty. Each list is stored in a doubly
linked list together with its size, Counti [v]. Using appropriate pointers, we can insert or
delete a given node to or from a concerned list in constant time.
2. The counter Level[v] keeps track of the level of the node v.
Algorithm. If a node violates one of the conditions of an (α, d, L)-decomposition (see Definition 2.5), then we call the node “dirty”, else the node is called “clean”. Specifically a node y at
level ℓ(y) = i is dirty iff either Dy (Zi ) > αd or Dy (Zi−1 ) < d. Initially, the input graph G = (V, E)
is empty, every node v ∈ V is at level 1, and every node is clean.
When an edge (u, v) is inserted/deleted, we first update the Friends lists of u and v by adding
or removing neighbors in constant time. Next we check whether u or v are dirty. If so, we run
the RECOVER() procedure described in Figure 1. Note that a single iteration of the While loop
(Steps 01-05) may change the status of some more nodes from clean to dirty (or vice versa). If and
when the procedure terminates, however, every node is clean by definition.
Analyzing the space complexity. Since each edge in G appears in two linked lists (corresponding to each of its endpoints), the space complexity of the data structure is O(n + m), where
m = |E|.
13

01.
02.
03.
04.
05.

While there exists a dirty node y
If Dy (Zℓ(y) ) > αd and ℓ(y) < L, Then
Increment the level of y by setting ℓ(y) ← ℓ(y) + 1.
Else if Dy (Zℓ(y)−1 ) < d and ℓ(y) > 1, Then
Decrement the level of y by setting ℓ(y) ← ℓ(y) − 1.
Figure 1: RECOVER().

Analysis of the Update Time. Each update operation takes constant time plus the time for
the RECOVER() procedure. We show below that the total time spent in procedure RECOVER()
during t update operations is O(tL/ǫ).
Potential Function. To determine the amortized update time we use a potential function B. Let
f (u, v) = 1 if l(u) = l(v) and let it be 0 otherwise. We define B and the node and edge potentials
Φ(v) and Ψ(u, v) as follows.
B =

X

Φ(v) +

v∈V

ℓ(v)−1

Φ(v) =

X

Ψ(e)

(1)

e∈E

1 X
max(0, αd − Dv (Zi )) for all nodes v ∈ V
ǫ

(2)

i=1

Ψ(u, v) = 2(L − min(ℓ(u), ℓ(v))) + f (u, v) for all edges (u, v) ∈ E

(3)

It is easy to check that all these potentials are nonnegative, and that they are uniquely defined
by the partition V1 , . . . , VL of the set of nodes V . Initially, the input graph G is empty and the
total potential B is zero. We show that (a) insertion/deletion of an edge (excluding subroutine
RECOVER()) increases the total potential by at most 3L/ǫ, and (b) for each unit of computation performed by procedure RECOVER() in Figure 1, the total potential decreases by at least
Ω(1). Since the total potential remains always nonnegative, these two conditions together imply
an amortized update time of O(L/ǫ).
Insertion. The insertion of edge (u, v) creates a new potential Ψ(u, v) with value at most 3L.
Further, the potentials Φ(u) and Φ(v) do not increase, and the potentials associated with all other
nodes and edges remain unchanged. Thus, the net increase in the potential B is at most 3L.

Deletion. The deletion of edge (u, v) destroys the (nonnegative) potential Ψ(u, v). Further, each
of the potentials Φ(u) and Φ(v) increases by at most L/ǫ, and the potentials of all other nodes and
edges remain unchanged. Thus, the net increase in the potential B is at most 2L/ǫ.
It remains to relate the change in the potential B with the amount of computation performed. See
Section 4.1.2. For ease of exposition, we first describe a high level overview of the analysis.
4.1.1

A high level overview of the potential function based analysis

The intuition behind this potential function is as follows. We maintain a data structure so that the
change of the level of a node y from i to i + 1 or from i to i − 1 takes time O(1 + Dy (Zi )). Ignoring
the constant factor (as we can multiply the potential function by this constant), we assume in
the following that the cost is simply 1 + Dy (Zi ). The basic idea is that the insertion or deletion
of an edge should increase the potential function in order to pay for all future level changes. To
14

implement this idea (1) each node gets a potential that increases when an adjacent edge is deleted
and that will pay for future level decreases of the node, and (2) each edge in G gets a potential
that pays for future level increases of its end points. We explain how we implement this in more
detail next: We know that when a node moves up to level i + 1 it has degree at least αd to nodes
in Zi , while when it moves back down it has degree at most d to nodes in Zi . Assuming that the
drop in the nodes degree was caused by the deletion of adjacent edges, the difference of the two, i.e.
(α − 1)d has to be used to pay for the cost of a level decreases of a node, which is 1 + Dy (Zi ) ≤ d.
This is possible if we set α ≥ 2. The value of α can even be reduced by multiplying the potential
of each node by 1/ǫ. Then the drop in potential is (α − 1)d/ǫ while the cost is only of d.
There is, however, an additional complication in this scheme, which forces us to set α = 2+Θ(ǫ):
A node on level i might not only decrease its level because of edge deletions (of edges to nodes on
level i or higher), but also if a node on level i moves down to level i − 1. Said differently, the drop
of (α − 1)d/ǫ of the degree of a node y on level i might not only be caused by edge deletions, but
also by the level drop of incident nodes. Thus, when the level of a node y decreases, the potential
of all its neighbors on a larger level has to increase by 1/ǫ to pay for their future level decrease.
Thus the drop of the potential of y by (α − 1)d/ǫ has to “pay” for the increase of the potential
of its neighbors, which is in total at most d/ǫ, and the cost of the operation, which is d. This is
possible if we set α = 2 + ǫ.
4.1.2

Analyzing the subroutine RECOVER().

We will analyze any single iteration of the While loop in Figure 1. During this iteration, a dirty
node y either increments its level by one unit, or decrements its level by one unit. Accordingly, we
consider two possible events.
Event 1: A dirty node y changes its level from i to (i + 1).
First, we upper bound the amount of computation performed during this event. Our algorithm
scans through the list Friendsi [y] and identifies the neighbors of y that are at level (i+1) or above.
For every such node x ∈ Ny ∩ Zi+1 , we need to (a) remove y from the list Friendsi [x] and add
y to the list Friendsi+1 [x], (b) increment the counter Counti+1 [x] by one unit, (c) add x to the
list Friendsi+1 [y] and remove x from the list Friendsi [y], (d) decrement the counter Counti [y]
by one unit and increment the counter Counti+1 [y] by one unit. Finally, we set Level[y] ← i + 1.
Overall, O(1 + Dy (Zi )) units of computation are performed during this event.
Next, we lower bound the net decrease in the B due to this event. We first discuss the node
potentials.
• (a) Since the node y gets promoted to level i + 1, we must have Dy (Zi ) > αd, which implies
that max(0, αd − Dy (Zi )) = 0, so that the potential Φ(y) does not change.
• (b) The potential of a node x ∈ Ny can only decrease.
• (b) The potential of a node x ∈
/ {y ∪ Ny } does not change.
P
Accordingly, the sum v∈V Φ(v) does not increase.

Next we consider the edge potentials. Towards this end, we first consider the edges incident upon
y. Specifically, consider a node x ∈ Ny .
• If ℓ(x) < i, the potential of the edge (x, y) does not change.
15

• If ℓ(x) = i, the potential of (x, y) is 2(L−i)+1 before the level change and 2(L−i) afterwards,
i.e., the potential drops by one.
• If ℓ(x) = i+ 1, the potential of (x, y) is 2(L − i) before the level change and 2(L − (i+ 1))+ 1 =
2(L − i) − 1 afterwards, i.e., it drops by one.
• If ℓ(x) > i + 1, the potential of (x, y) is 2(L − i) before the level change and 2(L − (i + 1))
afterwards, i.e., it drops by two.
P
The potentials associated with all other edges remain unchanged. Thus, the sum e∈E Ψ(e) drops
by at least Dy (Zi ).
We infer that the net decrease in the overall potential B is at least Dy (Zi ). Note that Dy (Zi ) > 0
(for otherwise the node y would not have been promoted to level i + 1). It follows that the net
decrease in B is sufficient to pay for the cost of the computation performed, which, as shown above,
is O(1 + Dy (Zi )).
Event 2: A dirty node y changes its level from level i to (i − 1).
First, we upper bound the amount of computation performed during this event. Our algorithm
scans through the nodes in the list Friendsi [y]. For each such node x ∈ Ny ∩ Zi , we need to (a)
remove y from the list Friendsi [x] and add y to the list Friendsi−1 [x] and (b) decrement the
counter Counti [x]. Finally, we need to add all the nodes in Friendsi [y] to the list Friendsi−1 [y],
make Friendsi [y] into an empty list, and set Counteri [y] to zero. Finally, we set Level[y] ← i−1.
Overall, O(1 + Dy (Zi )) units of computation are performed during this event.
Next, we lower bound the net decrease in the overall potential B due to this event. We first consider
the changes in the node potentials.
• (a) Since the node y was demoted to level i − 1, we must have Dv (Zi−1 ) < d. Accordingly,
the potential Φ(y) drops by at least (α − 1) · (d/ǫ) units due to the decrease in ℓ(y).
• (b) For every neighbor x of y, Dx (Zi ) decreases by one while Dx (Zj ) for j 6= i is unchanged.
The potential function of a node x considers only the Dx (Zj ) values if j < ℓ(x). Thus, only
for neighbors x with ℓ(x) >P
i does the potential function change, specifically it increases by
at most 1/ǫ. Thus the sum x∈Ny Φ(x) increases by at most Dy (Zi+1 )/ǫ. Further, note that
Dy (Zi+1 )/ǫ ≤ Dy (Zi−1 )/ǫ < d/ǫ. The last inequality holds since the node y was demoted
from level i to level (i − 1).
• The potential Φ(x) remains unchanged for every node x ∈
/ {y} ∪ Ny .
P
Thus, the sum v∈V Φ(v) drops by at least (α − 1) · (d/ǫ) − (d/ǫ) = (α − 2) · (d/ǫ).

We next consider edge potentials. Towards this end, we first consider the edges incident upon y.
Specifically, consider any node x ∈ Ny .
• If ℓ(x) < i − 1, the potential of the edge (x, y) does not change.
• If ℓ(x) = i−1, the potential of (x, y) is 2(L−(i−1)) before the level change and 2(L−(i−1))+1
afterwards, i.e., the potential increases by one.
• If ℓ(x) = i, the potential of (x, y) is 2(L − i) + 1 before the level change and 2(L − (i − 1)) =
2(L − i) + 2 afterwards, i.e., it increases by one.
16

• If ℓ(x) ≥ i + 1, the potential of (x, y) is 2(L − i) before the level change and 2(L − (i − 1))
afterwards, i.e., it increases by two.
P
The potentials associated with all other edges remain unchanged. Thus, the sum e∈E Ψ(e) increases by at most 2Dy (Zi−1 ) < 2d.
We infer that the overall potential B drops by at least (α − 2) · (d/ǫ) − 2d = (α − 2 − 2ǫ) · (d/ǫ).
Accordingly, for α ≥ 2 + 3ǫ this potential drop is at least d ≥ Dy (Zi ) + 1. We conclude that the net
drop in the overall potential B is again sufficient to pay for the cost of the computation performed.
This concludes the proof of Theorem 4.2.

5

A Semi-Streaming Algorithm with Fast Update and Query times

In Section 3, we presented a semi-streaming algorithm that maintains a (2 + ǫ)-approximation of
ρ∗ (G). Specifically, the algorithm can process a dynamic stream of updates (edge insertions/deletions)
using only Õ(n) bits of space. Unfortunately, however, it has a large update time of Θ̃(n), and it
answers a query only at the end of the stream (also in time Θ̃(n)).
On the other hand, in Section 4 we presented an algorithm that maintains a (4+ǫ)-approximation
of ρ∗ (G). This algorithm has the advantage of having very fast (i.e., Õ(1)) update and query times.
Furthermore, it can answer a query at any given time-instant (even in the middle of the stream).
But, unlike the algorithm from Section 3 whose space complexity is Õ(n), it has to store all the
edges and requires Θ̃(m + n) bits of space.
In this section, we combine the techniques from Sections 3 and 4 to get a result that captures the
best of both worlds. Specifically, we present a new algorithm that maintains a (4+ǫ)-approximation
of ρ∗ (G) while processing a stream of updates (edge insertions/deletions). We highlight that:
• The algorithm has very fast (i.e., Õ(1)) update and query times.
• It requires very little (i.e., Õ(n)) space.
• It can answer a query at any time-instant (i.e., even in the middle of the stream).

5.1

An Overview of Our Result

We denote the input graph by G = (V, E). It has |V | = n nodes, and in the beginning of our
algorithm the graph is empty (i.e., E = ∅). Subsequently, our algorithm processes a “stream of
updates” in the graph. Each update consists of an edge insertion/deletion. Specifically, at each
“time-step”, either an edge is inserted into the graph or an already existing edge is deleted from the
graph. The node set of the graph, however, remains unchanged over time. For any integer t ≥ 0,
we let G(t) = (V, E (t) ) denote the status of the input graph at time-step t (i.e., after the tth edge
insertion/deletion). Thus, G(0) = (V, E (0) ) denotes the status of G in the beginning, which implies
that E (0) = ∅. Further, we let m(t) = |E (t) | denote the number of edges in the graph G(t) . Finally,
Opt(t) = ρ(G(t) ) gives the value of the densest subgraph in G(t) . We also use the notations and
concepts introduced in Section 2. Our algorithm will maintain a value Output(t) at each time-step
t. We want Output(t) to be a (4 + ǫ)-approximation to Opt(t) .

17

Throughout Section 5, we fix the symbols ǫ, α, L, c, λ and T as defined below.

∗

∗

ǫ ∈ (0, 1) has a sufficiently small positive value.

(4)

L = 2 + ⌈log(1+ǫ) n⌉

(6)

α = 2 + Θ(ǫ) = 2 + c · ǫ, where c is some constant independent of ǫ (to be decided later).

λ ≥ 1 is any positive constant, and c is a constant such that c >> λ.
λ

T = ⌈n ⌉

(5)
(7)
(8)

We use the symbols Õ(.) and Θ̃(.) to hide poly(log n, 1/ǫ) factors. We now state the main result.
Theorem 5.1. Define T as in equation 8. There is an algorithm that processes a stream of T
updates (starting from an empty graph), and satisfies the following properties with high probability:
• It uses only Õ(n) bits of space.
• The total time taken to process the T edge insertions/deletions is Õ(T ). Thus, it has an
amortized update time of Õ(1).
• It maintains a value Output(t) such that for all time-steps t ∈ [1, T ] we have Output(t) ≤
Opt(t) ≤ (4 + ǫ) · Opt(t) . Thus, the algorithm maintains a (4 + ǫ)-approximation to the value
of the densest subgraph while processing the stream of updates, and the query time is O(1).
Note that the algorithm in Theorem 5.1 works only for polynomially many time-steps (since
T = Θ(nλ ) and λ is a constant). In contrast, we did not impose this restriction while presenting
our semi-streaming algorithm in Section 3. To see why this is the case, recall that a semi-streaming
algorithm maintains a “sketch” of the input while processing the stream of edge insertions/deletions.
For our algorithm in Section 3, the sketch is simply the collection of random samples from the edge
set of the input graph. Let Sketch(t) denote the status of the sketch at time-step t (i.e., it
corresponds to the graph G(t) ). Now, the following condition holds in Section 3:
• (P1) Fix any time-step t. With high probability, if we run the procedure in Section 3 on
Sketch(t) , then this gives us a good approximation to the value of Opt(t) .
A semi-streaming algorithm typically needs to invoke property (P1) only at the end of the stream,
since it answers a query after processing all the edge insertions/deletions. In this section, however,
we want an algorithm that can answer a query at any given time-instant (i.e., even in the middle
of the stream). Thus, we want the stronger property stated below.
• (P2) The following event holds with high probability. For every time-step t ∈ [1, T ], we can
get a good approximation to Opt(t) using Sketch(t) .
Intuitively, (P2) follows if we take a union bound over the complement of (P1) for all time-steps
t ∈ [1, T ]. But this can be done only if the length of the interval [1, T ] is bounded by some
polynomial in n. Thus, we require that T = Θ(nλ ) for some constant λ.
5.1.1

Main technical challenges

At a very high level, the following approach seems natural for proving Theorem 5.1. First, using
the techniques from Section 3, maintain Õ(n) uniformly random samples from the edge set of the
input graph. Next, using the techniques from Section 4, maintain (α, d, L)-decompositions on these
randomly sampled edges. The first step should ensure that the algorithm requires only Õ(n) bits
18

of space, while the second step should ensure that the algorithm requires Õ(1) update and query
times. Unfortunately, however, to implement this simple idea we need to overcome several intricate
technical challenges. They are described below.
1. As stated at the end of Section 3, maintaining the random samples from the edge set E
requires Θ̃(n) update time, since to process the insertion/deletion of an edge we have to
update Θ̃(n) many ℓ0 -samplers. So the first challenge is to speed up the update time of the
subroutine that maintains the randomly sampled edges. This is done in Section 5.2.
2. The algorithm in Section 3 uses one crucial observation that is captured in Lemma 2.3.
Specifically, the maximum density of a subgraph of G = (V, E) lies in the range [m/n, n],
where m = |E| and n = |V |. Thus, we set π = m/(2αn) and σ = 2(1 + ǫ)n, so that we have
α · π < d∗ < σ/(2(1 + ǫ)), where d∗ = maxS⊆V ρ(S) is the value of the maximum density
of a subgraph of G (see the discussion immediately after the proof of Lemma 3.2). Then
we discretize the range [π, σ] in powers of (1 + ǫ), by defining the values dk , k ∈ [K], as
per Corollary 2.7. For each k ∈ [K], we construct an (α, dk , L)-decomposition. Finally, we
approximate the value of d∗ by looking at the topmost levels (i.e., the node set VL ) of each of
these decompositions. To implement this approach in Section 3, we wait till the end of the
stream to get the value of m after all insertions/deletions. This is of crucial importance since
the degree-threshold dk (as per Corollary 2.7) for the kth (α, d, L)-decomposition depends on
the value of π, which, in turn, depends on m. In this section, however, we have to maintain
a solution at every time-step in the interval [1, T ]. Consequently, we have to maintain an
(α, dk , L)-decomposition for each k ∈ [K] throughout the interval [1, T ]. Hence, the degreethreshold dk of the kth decomposition changes over time as edges are inserted/deleted into
the input graph. Thus, we need to extend the dynamic algorithm from Section 4.1 (which
maintains an (α, d, L)-decomposition for a fixed d) so that it can handle the scenario where
d changes over time. See Section 5.5 for further details.
3. Suppose that we want to construct an (α, d, L)-decomposition using Õ(n) bits of space. In
Section 3, to achieve this goal we used a collection of sets {Si }, i ∈ {1, . . . , L − 1}. Recall the
proof of Lemma 3.2 for details. Specifically, each Si consisted of Θ(m log n/d) many uniformly
random samples from the edge set E. Given the subset of nodes Zi , we used the samples Si
to construct the next subset Zi+1 ⊆ Zi . Thus, we used different collections of sampled edges
for different levels of the (α, d, L)-decomposition. The reason behind this was as follows: For
the proof of Lemma 3.2 to be valid, it was crucial that the samples used for defining the set
Zi+1 be chosen independently of the samples used for the sets Z1 , . . . , Zi . This is in sharp
contrast to our dynamic algorithm in Section 4.1 for maintaining an (α, d, L)-decomposition:
that algorithm uses the same edge set E for different levels of the decomposition. Thus,
we need to find a way to extend the potential function based analysis from Section 4.1 to a
setting where different levels of the (α, d, L)-decomposition are concerned with different sets
of edges (chosen uniformly at random). See Section 5.5 for further details.
Roadmap for the rest of Section 5.

The rest of this section is organized as follows.

• In Section 5.2, we show how to maintain random samples from the edge set of the input
graph in Õ(n) space and Õ(1) update time. For technical reasons, we have to run two
separate algorithms for this purpose. Roughly speaking, the first algorithm (as stated in
Theorem 5.2) maintains the entire edge set of the graph whenever m(t) = Õ(n), whereas the
second algorithm (as stated in Theorem 5.3) maintains Θ̃(n) random samples from the edge
set of the graph whenever m(t) = Ω̃(n).
19

• In Section 5.3, we present a high level overview of our main algorithm. The main idea is to
classify each time-step as either “dense” or “sparse”, depending on the number of edges in
the input graph. This classification is done in such a way that Theorem 5.2 applies to all
sparse time-steps, whereas Theorem 5.3 applies to all dense time-steps.
• In Section 5.4, we present our algorithm for maintaining a (4 + ǫ)-approximation to Opt(t)
during all the sparse time-steps (see Theorem 5.4). This algorithm takes as input the set of
edges maintained by the subroutine from Theorem 5.2.
• In Section 5.5, we present our algorithm for maintaining a (4 + ǫ)-approximation to Opt(t)
during all the dense time-steps (see Theorem 5.5). This algorithm takes as input the set of
edges maintained by the subroutine from Theorem 5.3.
• Theorem 5.1 follows from Theorem 5.2 and Theorem 5.3.

5.2

Maintaining the randomly sampled edges in Õ(1) update time

Intuitively, we want to maintain s uniformly random samples from the edge-set E of the input
graph G = (V, E), for some s = Θ̃(n). In Section 3, we achieved this by running Θ̃(n) mutually
independent copies of the ℓ0 -sampler. This ensured a space complexity of Θ̃(n). However, after
each edge insertion/deletion in the input graph, we had to update each of the ℓ0 -samplers. So the
update time of our algorithm became Θ̃(n). In this section, we show how to bring down this update
time (for maintaining the randomly sampled edges) to Θ̃(1) without compromising on the space
complexity.
To see the high level idea behind our approach, suppose that the input graph has a large number
of edges, i.e., s ≪ m = |E|. We maintain s “buckets” B1 , . . . , Bs . Whenever an edge e is inserted
into the input graph, we insert the edge into a bucket chosen uniformly at random. When the edge
gets deleted from the input graph, we also delete it from the bucket it was assigned to. Thus, the
buckets B1 , . . . , Bs give a random partition of the edge set of the input graph G = (V, E). We can
maintain this partition using an appropriate hash function. Now, we run s mutually independent
copies of the ℓ0 sampler, one for each bucket Bi , i ∈ {1, . . . , s}. Let S be the collection of edges
returned by these ℓ0 -samplers. Thus, we have S ⊆ E, |S| = s, and any given edge e ∈ E belongs to
S with a probability that is very close to s/m. In other words, the set S is a set of s edges chosen
uniformly at random from the edge set E (without replacement). This solves our problem. The
space requirement is Θ̃(s) = Θ̃(n) since we run s copies of the ℓ0 -sampler and each of this samplers
needs Θ̃(1) space. Furthermore, unlike our algorithm in Section 3, here if an edge insertion/deletion
takes place in the input graph G, then we only need to update a single ℓ0 sampler (the one running
on the bucket that edge was assigned to). This improves the update time to Θ̃(1).
To be more specific, we present two results in this section. In Theorem 5.2, we show how to
maintain the edge set of the input graph G = (V, E) at all time-steps where it is “sparse” (i.e.,
m = |E| is small). Next, in Theorem 5.3, we show how to maintain Θ̃(n) uniformly random samples
(without replacement) from the edge set E at all time-steps where the input graph is “dense”
(i.e., m = |E| is large). The proofs of Theorems 5.2 and 5.3 appear in Sections 5.2.1 and 5.2.2
respectively. Both the proofs crucially use well known results on ℓ0 -sampling in a streaming setting
(see Lemma 2.8) and w-wise independent hash functions (see Lemma 2.9).
Theorem 5.2. Starting from an empty graph, we can process the first T updates in a dynamic
stream so as to maintain a random subset of edges F (t) ⊆ E (t) at each time-step t ≤ T . This
requires Õ(n) space and Õ(1) worst case update time. Furthermore, the following conditions hold

20

with high probability.
F (t) = E (t) at each time-step t ≤ T with m(t) ≤ 8αc2 n log2 n.

(9)

Note that the proof of Theorem 5.2 is by no means obvious, for the following reason. It might
happen that we have not included an edge e from the input graph in our sample (since the graph
currently contains many edges). However, with the passage of time, a lot of edges get deleted from
the graph so as to make it sparse, and at that time we might need to recover the edge e.
Theorem 5.3. Fix any positive integer s ≤ 2αcn log n. Starting from an empty graph, we can
process the first T updates in a dynamic stream so as to maintain a random subset of edges S (t) ⊆
E (t) at each time-step t ∈ [T ]. This requires Õ(n) space and Õ(1) worst case update time. For
(t)
every edge e ∈ E (t) , let Xe ∈ {0, 1} be an indicator random variable that is set to one iff e ∈ S (t) .
Then we have:
1. The following condition holds with high probability.
i h
h
s i
E Xe(t) ∈ (1 ± ǫ) · (t) for all edges e ∈ E (t) , at each t ≤ T with m(t) ≥ 4αc2 n log2 n.
m
(10)
(t)

2. At each time-step t ≤ T , the random variables {Xe }, e ∈ E (t) , are negatively associated.
3. Insertion/deletion of an edge in G leads to at most two insertion/deletions in the set S.
5.2.1

Proof of Theorem 5.2

The algorithm. We define w = q = 8αc2 n log2 n, and build a w-wise independent hash function
h : E ∗ → [w] as per Lemma 2.9. This requires Õ(n) space, and the hash value h(e) for any given
(t)
e ∈ E ∗ can be evaluated in O(1) time. For all t ∈ [T ] and i ∈ [w], let Bi denote the set of edges
(t)
(t)
e ∈ E (t) with h(e) = i. So the edge set E (t) is partitioned into w random subsets B1 , . . . , Bw .
As per Lemma 2.8, for each i ∈ [w] we run r = c2 log2 n copies of a subroutine called
Streaming-Sampler. Specifically, for every i ∈ [w] and j ∈ [r], the subroutine Streaming(t)
Sampler(i, j) maintains a uniformly random sample from the set Bi in Õ(1) space and Õ(1) worst
case update time. Furthermore, the subroutines {Streaming-Samplers(i, j)}, i ∈ [w], j ∈ [r], use
mutually independent random bits. Let Y (t) denote the collection of the random samples maintained by all these Streaming-Samplers. Since we have multiple Streaming-Samplers running
(t)
on the same set Bi , i ∈ [w], a given edge can occur multiple times in Y (t) . We define F (t) ⊆ E (t) to
be the collection of those edges in E (t) that appear at least once in Y (t) . Our algorithm maintains
the subset F (t) at each time-step t ∈ T .

Update time. Suppose that an edge e is inserted into (resp. deleted from) the graph G = (V, E)
at time-step t ∈ [T ]. To handle this edge insertion (resp. deletion), we first compute the value
(t)
i = h(e) in constant time. Then we insert (resp. delete) the edge to the set Bi , and call the
subroutines Streaming-Sampler(i, j) for all j ∈ [r] so that they can accordingly update the
random samples maintained by them. Each Streaming-Sampler takes Õ(1) time in the worst
case to handle an update. Since r = O(log2 n), the total time taken by our algorithm to handle an
edge insertion/deletion is O(r poly log n) = Õ(1).

Space complexity. We need Õ(1) space to implement each Streaming-Sampler(i, j), i ∈
[w], j ∈ [r]. Since w = O(n log2 n) and r = O(log2 n), the total space required by all the streaming
samplers is O(wr poly log n) = Õ(n). Next, note that we can construct the hash function h using
Õ(n) space. These observations imply that the total space requirement of our scheme is Õ(n).
21

Correctness. It remains to show that with high probability, at each time-step t ∈ [T ] with
m(t) ≤ 8αc2 n log2 n, we have F (t) = E (t) .

Fix any time-step t ∈ [T ] with m(t) ≤ 8αc2 n log2 n. Consider any i ∈ [w]. The probability
2
2
that any given edge e ∈ E (t)
h has ih(e) = i is equal to 1/w. Since w = 8αc n log n, the linearity of
(t)
expectation implies that E |Bi | = m(t) /w ≤ 1. Since the hash function h is w-wise independent,
(t)

and since m(t) ≤ w, we can apply the Chernoff bound and infer that |Bi | ≤ c log n with high
probability. Now, a union bound over all i ∈ [w] shows that with high probability, we have
(t)
|Bi | ≤ c log n for all i ∈ [w]. Let us call this event E (t) .
Condition on the event E (t) . Fix any edge e ∈ E (t) . Let h(e) = i, for some i ∈ [w]. We
(t)
(t)
know that e ∈ Bi , that there are at most c log n edges in Bi , and that our algorithm runs
(t)
r = c2 log2 n many Streaming-Samplers on Bi . Each such Streaming-Sampler maintains
(t)
(independently of others) a uniformly random sample from Bi . Consider the event where the
edge e is not picked in any of these random samples. This event occurs with probability at most
2
2
(1 − 1/(c log n))c log n ≤ 1/nc .
In other words, conditioned on the event E (t) , an edge e ∈ E (t) appears in F (t) with high
probability. Taking a union bound over all e ∈ E (t) , we infer that F (t) = E (t) with high probability,
conditioned on the event E (t) . Next, we recall that the event E (t) itself occurs with high probability.
Thus, we get that the event F (t) = E (t) also occurs with high probability. To conclude the proof,
we take a union bound over all time-steps t ∈ [T ] with m(t) ≤ 8αc2 n log2 n.
5.2.2

Proof of Theorem 5.3

We define w = 2cs log n, q = s, and build a w-wise independent hash function h : E ∗ → [s] as
per Lemma 2.9. This requires Õ(n) space, and the hash value h(e) for any given e ∈ E ∗ can be
evaluated in O(1) time.
(t)
This hash function partitions the edge set E (t) into s mutually disjoint buckets {Bj }, j ∈ [s],
(t)

where the bucket Bj consists of those edges e ∈ E (t) with h(e) = j. For each j ∈ [s], we run an
independent copy of ℓ0 -Sampler, as per Lemma 2.8, that maintains a uniformly random sample
(t)
from Bj . The set S (t) consists of the collection of outputs of all these ℓ0 -Samplers. Note that
(a) for each e ∈ E ∗ , the hash value h(e) can be evaluated in constant time [37], (b) an edge
insertion/deletion affects exactly one of the buckets, and (c) the ℓ0 -Sampler of the affected bucket
can be updated in Õ(1) time. Thus, we infer that this procedure handles an edge insertion/deletion
in the input graph in Õ(1) time, and furthermore, since s = Õ(n), the procedure can be implemented
in Õ(n) space. We now show that this algorithm satisfies the three properties stated in Theorem 5.3.
1. Fix any time-step t ∈ [1, T ] where m(t) ≥ 4αc2 n log2 n. Since s ≤ 2αcn log n, we infer that
m(t) = |E (t) | ≥ 2cs log n. Hence, we can partition (purely
n
oas a thought experiment) the
(t)
(t)
edges in E into at most polynomially many groups Hj ′ , in such a way that the size

of each group lies between cs log n and 2cs log n. Thus, for any j ∈ [s] and any j ′ , we have
(t)
(t)
|Hj ′ ∩ Bj | ∈ [c log n, 2c log n] in expectation. Since the hash function h is (2cs log n)-wise
independent, by applying a Chernoff bound we infer that with high probability, the value
(t)
(t)
|Hj ′ ∩ Bj | is within a (1 ± ǫ) factor of its expectation. Applying the union bound over all
o
n
(t)
(t)
are within a
j, j ′ , we infer that with high probability, the sizes of all the sets Hj ′ ∩ Bj
(t)

(1±ǫ) factor of their expected values – let us call this event R(t) . Note that E[|Bj |] = m(t) /s
22

P
(t)
(t)
(t)
(t)
and |Bj | = j ′ |Bj ∩ Hj ′ |. Hence, under the event R(t) , for all j ∈ [s] the quantity |Bj |
is within a (1 ± ǫ) factor of m(t) /s. Under the same event R(t) , due to the ℓ0 -Samplers, the
probability that a given edge e ∈ E (t) with h(e) = j (say) becomes part of S (t) is within a
(t)
(1 ± ǫ) factor of 1/|Bj |, which, in turn, is within a (1 ± ǫ) factor of s/m(t) . This implies that
i
h

 

(t)
for any given edge e ∈ E (t) , we have E Xe = Pr e ∈ S (t) ∈ (1 ± ǫ) · s/m(t) with high
probability.
2. The property of negative association follows from the facts that (a) if two edges are hashed to
(t)
different buckets, then they are included in Si in a mutually independent manner, and (b)
(t)
if they are hashed to the same bucket, then they are never simultaneously included in Si .
3. Finally, when an edge e is inserted into (resp. deleted from) the input graph, only the ℓ0 sampler running on the bucket Bj , for j = h(e) gets affected. This implies that a single edge
insertion/deletion in the input graph leads to at most two edge insertions/deletions in the
random subset of edges S ⊆ E.

5.3

A high level overview of our algorithm: Sparse and Dense Intervals

Our algorithm for Theorem 5.1 will consist of four different components. They are described below.
• (P1) This subroutine implements an algorithm as per Theorem 5.2.
• (P2) This subroutine implements Θ̃(1) independent copies of the algorithm in Theorem 5.3.
• (P3) For each t ∈ [1, T ], this subroutine classifies time-step t as either “dense” or “sparse”.
This is done on the fly, i.e., immediately after receiving the tth edge insertion/deletion in
G. Consequently, the range [1, T ] is partitioned into “dense” and “sparse” “intervals”, where
a dense (resp. sparse) interval is a maximal and contiguous block of dense (resp. sparse)
time-steps. For example, we say that [t0 , t1 ] ⊆ [1, T ] is a dense interval iff (a) time-step t
is dense for all t ∈ [t0 , t1 ], (b) either t0 = 1 or time-step (t0 − 1) is sparse, and (c) either
t1 = T or time-step (t1 + 1) is sparse. The sparse time-intervals are defined analogously. The
subroutine ensures the following properties.
1. We have m(t) ≤ 8αc2 n log2 n for every sparse time-step t ∈ [1, T ]. In other words, the
input graph has a small number of edges in a sparse time-step. Note that 8αc2 n log2 n
is also the threshold used in Theorem 5.2. Thus, with high probability, equation 9 holds
at all sparse time-steps.
2. We have m(t) ≥ 4αc2 n log2 n for every dense time-step t ∈ [1, T ]. In other words, the
input graph has a large number of edges in a dense time-step. Note that 4αc2 n log2 n is
also the threshold used in Theorem 5.3 (part 1). Thus, with high probability, equation 10
holds at all dense time-steps.
3. If a dense interval begins at a time-step t, then we have m(t) = 1 + 8αc2 n log2 n.
4. Every dense (resp. sparse) interval spans at least 4αc2 n log2 n time-steps, unless it is the
interval ending at T .
The classification of a time-step as dense or sparse is done according to the procedure outlined
in Figure 2. This procedure can be easily implemented in Θ̃(1) space and Θ(1) update time,
since all we need is a counter that keeps track of the number of edges in the input graph
while processing the stream of updates. Furthermore, it is easy to check that the procedure
in Figure 2 ensures all the four properties described above.
23

• (P4) This subroutine takes as input the set of edges maintained by (P1). Furthermore, it also
has access to the output of the subroutine (P3). At all sparse time-steps, it maintains a value
Output(t) that gives a (4 + ǫ)-approximation of Opt(t) . See Section 5.4 for further details.
• (P5) This subroutine takes as input the subsets of edges maintained by (P2). Furthermore,
it also has access to the output of the subroutine (P3). At all dense time-steps, it maintains
a value Output(t) that gives a (4 + ǫ)-approximation of Opt(t) . See Section 5.5 for further
details.
• Theorem 5.1 follows from Theorem 5.4 and Theorem 5.5.
01.
02.
03.
04.
05.
06.
07.
08.
09.
10.
11.
12.

The time-step 1 is classified as sparse.
For t = 2 to T
If time-step (t − 1) was sparse, Then
If m(t) ≤ 8αc2 n log2 n, Then
Classify time-step t as sparse.
Else if m(t) > 8αc2 n log2 n, Then
Classify time-step t as dense.
Else if time-step (t − 1) was dense, Then
If m(t) ≥ 4αc2 n log2 n, Then
Classify time-step t as dense.
Else if m(t) < 4αc2 n log2 n, Then
Classify time-step t as sparse.
Figure 2: CLASSIFY-TIME-STEPS(.).

5.4

Algorithm for sparse intervals

In this section, we show how to maintain a (4 + ǫ)-approximation to the value of the densest
subgraph during the sparse time-intervals. Specifically, we prove the following theorem.
Theorem 5.4. There is an algorithm that uses Õ(n) space and maintains a value Output(t) at
every sparse time-step t ≤ T . The algorithm gives the following two guarantees with high probability.
• Opt(t) /(4 + ǫ) ≤ Output(t) ≤ Opt(t) at every sparse time-step t ≤ T .
• The algorithm takes Õ(T ) time to process the stream of T updates in G. In other words, the
amortized update time is Õ(1).
The algorithm for Theorem 5.4 consists of two major ingredients.
• First, we run a subroutine as per Theorem 5.2 while processing the stream of T updates.2 This
ensures that with high probability, we maintain a subset F (t) ⊆ E (t) such that F (t) = E (t)
at every sparse time-step t ≤ T . The worst case update time and space complexity of this
subroutine are Õ(1) and Õ(n) respectively.
2

Note that this is the same subroutine (P1) from Section 5.3.

24

• Second, we run our dynamic algorithm – which we refer to as Dynamic-algo – from Section 4
on the graph (V, F (t) ) during every sparse time-interval.3 Since F (t) = E (t) throughout the
(t)
i (with high probability), this allows us to maintain an Output ∈
hduration of such an interval
Opt(t) /(4 + ǫ), Opt(t) at every sparse time-step t ≤ T . As the input graph has Õ(n) edges
at every sparse time-step, the space complexity of Dynamic-algo is Õ(n).

It remains to analyze the amortized update time of Dynamic-algo. Towards this end, fix any
sparse time-interval [t0 , t1 ], and let C(t0 , t1 ) denote the amount of computation performed during
this interval by the subroutine Dynamic-algo. Consider two possible cases.
• Case 1. (t1 < T )

In this case, our analysis from Section 4 implies that C(t0 , t1 ) = Õ(n + (t1 − t0 )). Since
t1 < T , the subroutine (P3) from Section 5.3 ensures that (t1 − t0 ) = Ω(n).4 This gives us
the guarantee that C(t0 , t1 ) = Õ(t1 − t0 ).

• Case 2. (t1 = T )

In this case, the sparse time-interval under consideration ends at T . Thus, if (t1 − t0 ) = o(n),
then we would have C(t0 , t1 ) = Õ(n). Else if (t1 − t0 ) = Ω(n), then applying a similar
argument as in Case 1, we get C(t0 , t1 ) = Õ(t1 − t0 ).


Let ti0 , ti1 denote the ith sparse time-interval, and let C denote the amount of computation performed by Dynamic-algo during the entire time-period [1, T ]. Since the sparse time-intervals are
mutually disjoint, and since there can be at most one sparse time-interval that ends at T , we get
the following guarantee.
!
X
i
i
C =
(11)
Õ((t1 − t0 )) + Õ(n) ≤ Õ(T ) + Õ(n) = Õ(T )
i

The last equality holds as T = Θ(nλ ) and λ ≥ 1 (equation 7). This shows that the amortized
update time of the algorithm is Õ(1), thereby concluding the proof of Theorem 5.4.

5.5

Algorithm for dense intervals

In this section, we show how to maintain a (4 + ǫ)-approximation to the value of the densest
subgraph during the dense time-intervals. Specifically, we prove the following theorem.
Theorem 5.5. There is an algorithm that uses Õ(n) space and maintains a value Output(t) at
every dense time-step t ≤ T . The algorithm gives the following two guarantees with high probability.
• Opt(t) /(4 + ǫ) ≤ Output(t) ≤ Opt(t) at every dense time-step t ≤ T .
• The algorithm takes Õ(T ) time to process the stream of T updates in G. In other words, the
amortized update time is Õ(1).
3
4

We can identify each sparse time-interval using the subroutine (P3) from Section 5.3.
See item 4 in the description of the subroutine (P3).

25

5.5.1

Basic building block for proving Theorem 5.5

For every time-step t ∈ [1, T ], we define:
π (t) = m(t) /(2αn), and σ = 2(1 + ǫ)n

(12)

Accordingly, Lemma 2.3 implies that:
α · π (t) < Opt(t) < σ/(2(1 + ǫ))

(13)

We now discretize the range [π (t) , σ] in powers of (1 + ǫ) as in Corollary 2.7. Specifically, we define:

(t)

K = 2 + ⌈log(1+ǫ) (σ · (2αn))⌉

(14)

dk = (1 + ǫ)k−1 · π (t) for all k ∈ [K]

(15)

Note that m(t) ≥ 1 at every dense time-step t ≤ T . This ensures that π (t) ≥ 1/(2αn), and hence
we have K ≥ 2 + ⌈log(1+ǫ) (σ/π (t) )⌉ during those time-steps. In other words, the values of π (t) , σ
and K satisfy the condition stated in Corollary 2.7 during the dense time-intervals. Also note that
the value of K does not depend on the time-step t under consideration.5 Furthermore, we have
K = Õ(1).
We want to maintain a 2α(1 + ǫ)3 = (4 + Θ(ǫ))-approximation of the maximum density during
(t)
the dense time-intervals. For this purpose it suffices to maintain an (α, dk , L)-decomposition of
G(t) for each k ∈ [K] (see Corollary 2.7).
Thus, we conclude that Theorem 5.5 follows from Theorem 5.6. Accordingly, for the rest of
Section 5.5, we fix an index k ∈ [K], and focus on proving Theorem 5.6.
Theorem 5.6. Fix any integer k ∈ [K]. There is a dynamic algorithm that uses Õ(n) bits of space
(t)
(t)
and maintains L subsets of nodes V = Z1 ⊇ · · · ⊇ ZL at every dense time-step t ∈ [T ]. The
algorithm is randomized and gives the following two guarantees with high probability.
(t)

(t)

(t)

• The tuple (Z1 . . . ZL ) is an (α, dk , L)-decomposition of G(t) at every dense time-step t ∈ [T ].
• The algorithm takes Õ(T ) time to process the stream of T updates. In other words, the
algorithm has an amortized update time of Õ(1).
5.5.2

Overview of our algorithm for Theorem 5.6

Our algorithm for proving Theorem 5.6 consists of two major ingredients.
• First, at each dense time-step t ≤ T we maintain a collection of (L − 1) random subsets
(t)
(t)
of edges S1 , . . . , SL−1 ⊆ E (t) . To maintain these random subsets, we need to run (L − 1)
mutually independent copies of the algorithm in Theorem 5.3 (for an appropriate value of s).
(t)

(t)

(t)

• Second, using the random subsets S1 , . . . , SL−1 ⊆ E (t) , we maintain an (α, dk , L) decom(t)

(t)

(t)

position (Z1 , . . . , ZL ) during the dense time-steps. Specifically, we set Z1 = V . Next, for
(t)
(t)
(t)
(t)
i = 1 to (L−1), we construct the node set Zi+1 ⊆ Zi by looking at the degrees Dv (Zi , Si )
(t)

(t)

of the nodes v ∈ Zi among the edges e ∈ Si . This follows the spirit of the construction in
Section 3 (but note that there we did not concern ourselves with the update time).
(t)

5
This is especially important since we want to maintain an (α, dk , L)-decomposition for each k ∈ [K] during the
dense time-intervals. If K were a function of t, then the number of such decompositions would have varied over time.

26

(t)

(t)

From the proof of Lemma 3.2, we infer that each Si should contain s(t) = cm(t) log n/dk
random samples from the edge set E (t) . Equations 12 and 15 ensure that s(t) = 2αcn log n/(1+
ǫ)k−1 , which means that the value of s(t) is independent of the time-step t under consideration.
Accordingly, for the rest of Section 5.5, we omit the superscript t from s(t) and define:
(t)

s = 2αcn log n/(1 + ǫ)k−1 = cm(t) log n/dk for each dense time-step t ≤ T.

(16)

Furthermore, since k ≥ 1, we observe that:
s ≤ 2αcn log n

(17)

Thus, the value assigned to s satisfies the condition dictated by Theorem 5.3.
To summarize, our first subroutine maintains (L − 1) mutually independent copies of the algorithm
in Theorem 5.3 (for the value of s as defined by equations 16, 17). The random subsets of edges
(t)
(t)
maintained by them are denoted as S1 , . . . , SL−1 . Since L = Θ̃(1) (see equation 6), Theorem 5.3
ensures that this subroutine has Õ(1) worst case update time and Õ(n) space complexity.
Next, we present another subroutine Dynamic-stream (see Section 5.5.3) that
n isoinvoked only
(t)
6
during the dense time-intervals. This subroutine can access the random subsets Si
, i ∈ [L−1],
(t)

(t)

and it maintains L subsets of nodes V = Z1 ⊇ · · · ⊇ ZL at each dense time-step t ∈ [T ].

Roadmap.

The rest of Section 5.5 is organized as follows.

• In Section 5.5.3, we fix a dense time-interval [t0 , t1 ], and describe how the subroutine Dynamicstream processes the edge insertions/deletions in the input graph during this interval. We
(t)
show that Dynamic-stream maintains an (α, dk , L)-decomposition of the input graph G(t)
throughout the duration of this dense time-interval (see Lemma 5.8).
• Section 5.5.4 presents the data structures for implementing the subroutine Dynamic-stream.
• In Section 5.5.5, we make some preliminary observations about the running time of the
subroutine Dynamic-stream, and analyze its space complexity (see Lemma 5.9).
• In Section 5.5.6, we analyze the amortized update time of the subroutine Dynamic-stream
(see Corollary 5.14). Theorem 5.6 follows from Lemma 5.8, Lemma 5.9 and Corollary 5.14.
• In Sections 5.5.7 and 5.5.8 are devoted to the proof of two lemmas stated in Section 5.5.6.
5.5.3

The subroutine Dynamic-stream for a dense time-interval [t0 , t1 ]
(t)

Fix any dense time-interval [t0 , t1 ] ⊆ [1, T ]. We will maintain L subsets of nodes V = Z1 ⊇ · · · ⊇
(t)
ZL at each time-step t ∈ [t0 , t1 ]. With high probability, we will prove that throughout the interval
(t)
(t)
(t)
the tuple (Z1 , . . . , ZL ) remains a valid (α, dk , L)-decomposition of G(t) = (V, E (t) ).
We run (L − 1) mutually independent copies of the algorithm stated in Theorem 5.3 (for the
value of s as defined by equations 16, 17). Hence, at each time-step t ∈ [t0 , t1 ], we can access the
(t)
(t)
mutually independent random subsets of edges S1 , . . . , SL−1 ⊆ E (t) as defined in Section 5.5.2.
Initialization in the beginning of the dense time-interval [t0 , t1 ].

Just before time-step t0 , we perform the initialization step outlined in Figure 3. It ensures that
(t −1)
(t −1)
Z1 0
= V and Zi 0
= ∅ for all i ∈ {2, . . . , L}.
6

The dense time-intervals can be easily identified using the subroutine (P3) from Section 5.3.

27

01.
02.
03.

(t −1)

Set Z1 0
←V.
For i = 2 to L
(t −1)
Set Zi 0
← ∅.

Figure 3: INITIALIZE(.).
Handling an update in G during the dense time-interval [t0 , t1 ].
Consider an edge insertion/deletion in the input graph during time-step t ∈ [t0 , t1 ]. The edge set
E (t) is different from the edge set E (t−1) . Accordingly, for all i ∈ [L − 1], the subset of edges
(t)
(t−1)
Si may differ from the subset of edges Si
. Therefore, at this time we call the subroutine
(t−1)
(t−1)
RECOVER-SAMPLE(t) in Figure 4. Its input is the
, . . . , ZL ). Based
n oldodecomposition (Z1
on this old decomposition, and the new samples
(t)

(t)

(t)

Si

, i ∈ [L − 1], the subroutine constructs a

new decomposition (Z1 , . . . , ZL ).
As in Section 3, we want to ensure that the node set Zi is completely determined by the outcomes
of the random samples in {Sj }, j < i (see the proof of Lemma 3.2). Towards this end, we observe
the following lemma.
01.
02.
03.
04.
05.
06.
07.
08.
09.
10.

(t)

Set Z1 ← V .
For i = 1 to L
(t−1)
.
Set Yi ← Zi
For i = 1 to (L − 1)
(t)
(t)
(t)
(t)
Let Ai be the set of nodes y ∈ Zi having Dy (Zi , Si ) > (1 − ǫ)2 αc log n.
(t)
(t)
(t)
(t)
Let Bi be the set of nodes y ∈ Zi having Dy (Zi , Si ) < (1 + ǫ)2 c log n.
(t)
Set Yi+1 ← Yi+1 ∪ Ai .
For all j = (i + 1) to (L − 1)
(t)
Set Yj ← Yj \ Bi .
(t)
Set Zi+1 ← Yi+1 .

Figure 4: RECOVER-SAMPLE(t).
(t)

Lemma 5.7. Fix any time-step t ∈ [t0 , t1 ], any index i ∈ [L − 1], and consider the set Zi
defined by the procedure in Figure 4.
o
n
(t)
(t)
, j < i.
1. The node set Zi is completely determined by the contents of the sets Sj

as

o
n
(t)
(t)
, j ≥ i, are independent of the contents of the set Zi .
2. The contents of the random sets Sj

Proof. Follows from the description of the procedure in Figure 4.

We now prove the correctness of our algorithm. Specifically, we show that with high probability
(t)
(t)
(t)
the tuple (Z1 , . . . , ZL ) remains a valid (α, dk , L)-decomposition of the input graph throughout
the dense time-interval under consideration.
(t)

(t)

Lemma 5.8. With high probability, at each time-step t ∈ [t0 , t1 ] the tuple (Z1 . . . ZL ) maintained
(t)
by the subroutine Dynamic-stream gives an (α, dk , L)-decomposition of the input graph G(t) .
28

(t)

Proof. For each time-step t ∈ [t0 , t1 ] and index i ∈ [L − 1], we define an event Ei
(t)

• The event Ei

occurs iff the following two conditions hold simultaneously.

(t)

(t)

– Zi+1 ⊇ {v ∈ Zi
(t)

as follows.

(t)

– Zi+1 ∩ {v ∈ Zi

(t)

(t)

: Dv (Zi , E (t) ) > αdk }, and
(t)

(t)

: Dv (Zi , E (t) ) < dk } = ∅.

We now define another event E (t) for each time-step t ∈ [t0 , t1 ].
TL−1 (t)
Ei .
• E (t) = i=1
(t)

(t)

(t)

By Definition 2.5, the tuple (Z1 .h. . ZLi ) is an (α, dk , L)-decomposition of G(t) iff the event E (t)
(t)
≥ 1 − 1/(poly n) for any given i ∈ {1, . . . , L − 1} and
occurs. Below, we show that Pr Ei


t ∈ [t0 , t1 ]. Taking a union bound over all i ∈ {1, . . . , L − 1}, we get Pr E (t) ≥ 1 − 1/(poly n) at
each time-step t ∈ [t0 , t1 ]. Hence, the lemma follows by taking a union bound over all t ∈ [t0 , t1 ].
For the rest of the proof, fix any time-step t ∈ [t0 , t1 ] and index i ∈ {1, . . . , L − 1}.
(t)

• Fix any instance of the random set Zi

and condition on this event.
(t)

– By Theorem 5.3 and equation 16, each edge e ∈ E (t) appears in Si with probability
(t)
(1 ± ǫ)s/m(t) = (1 ± ǫ)c log n/dk . Furthermore, these events are negatively associated
(see Section 2.4).
(t)

(t)

(t)

Consider any node v ∈ Zi with Dv (Zi , E (t) ) > αdk . By linearity of expectation:
h
i
(t)
(t)
(t)
(t)
E Dv (Zi , Si ) ≥ αdk · (1 − ǫ)c log n/dk = (1 − ǫ)αc log n.
(t)

(t)

Since the contents of the random set Si are independent of the contents of Zi (see
Lemma 5.7), we can apply a Chernoff bound on this expectation, and derive that:
i
h
(t)
(t)
(t)
(18)
Pr Dv (Zi , Si ) > (1 − ǫ)2 αc log n | Zi ≥ 1 − 1/(poly n)
(t)

(t)

Now, Figure 4 implies that if Dv (Zi , Si ) > (1 − ǫ)2 αc log n, then the node v becomes
(t)
part of Zi+1 . Thus, applying equation 18 we get:
i
i
h
h
(t)
(t)
(t)
(t)
(t)
Pr v ∈ Zi+1 | Zi ≥ Pr Dv (Zi , Si ) > (1 − ǫ)2 αc log n | Zi ≥ 1 − 1/(poly n) (19)
(t)

Note that equation 19 would have been true even if v did not belong to Zi . Furthermore,
equation 19 holds regardless of the event E (t−1) .
(t)

(t)

(t)

Next, consider any node u ∈ Zi with Du (Zi , E (t) ) < dk . A similar argument shows:
i
i
h
h
(t)
(t)
(t)
(t)
Pr u ∈
/ Zi+1 | Zi ≥ Pr Du (Zi , E (t) ) < (1 + ǫ)2 c log n | Zi ≥ 1 − 1/(poly n) (20)
(t)

Note that equation 20 would have been true even if u did not belong to Zi . Furthermore,
equation 20 holds regardless of the event E (t−1) .
(t)

Thus, applying a union bound on equations 19, 20 over all nodes in Zi , we infer that:
i
h
(t)
(t)
Pr Ei | Zi ≥ 1 − 1/(poly n).
29

i
h
(t)
(t)
(t)
≥ 1 − 1/(poly n) holds for every possible instantiation of Zi ,
Since the guarantee Pr Ei | Zi
i
h
(t)
≥ 1 − 1/(poly n). Taking a union bound over all indices i ∈ {1, . . . , L − 1}, we
we get Pr Ei
 (t)  TL−1 (t)
infer that Pr E
= i=1 Ei ≥ 1 − 1/(poly n).
In other words, at every time-step t ∈ [t0 , t1 ] the event E (t) occurs with high probability, and
′
this holds regardless of the past events E (t ) , t′ < t. Hence, taking a union bound over all time-steps
(t)
(t)
in the interval [t0 , t1 ], we get: With high probability, for all t ∈ [t0 , t1 ] the tuple (Z1 . . . ZL )
(t)
maintained by the subroutine Dynamic-stream gives an (α, dk , L)-decomposition of the input
graph G(t) . This concludes the proof of the lemma.
5.5.4

Data structures for implementing the procedure in Figure 4

Recall the notations introduced in Section 2.
• Consider any node v ∈ V and any i ∈ {1, . . . , L − 1}. We maintain the doubly linked lists
{Friendsi [v, j]} , 1 ≤ j ≤ L − 1 as defined below. Each of these lists is defined by the
neighborhood of v induced by the sampled edges in Si . Recall Definition 2.5.
– If i ≤ ℓ(v), then we have:

∗ Friendsi [v, j] is empty for all j > i.
∗ Friendsi [v, j] = Nv (Zj , Si ) for j = i.
∗ Friendsi [v, j] = Nv (Vj , Si ) for all j < i.

– Else if i > ℓ(v), then we have:

∗ Friendsi [v, j] is empty for all j > ℓ(v).
∗ Friendsi [v, j] = Nv (Zj , Si ) for j = ℓ(v).
∗ Friendsi [v, j] = Nv (Vj , Si ) for all j < ℓ(v).
For every node v ∈ V , we maintain a counter Degreei [v], which keeps track of the number of
nodes in Friendsi [v, i]. Note that if ℓ(v) < i, then this counter equals zero. Further, we maintain
a doubly linked list Dirty-Nodes[i]. This consists
having either
 of all the nodes v ∈ V
2
2
Degreei [v] > (1 − ǫ) αc log n and ℓ(v) = i or Degreei [v] < (1 + ǫ) c log n and ℓ(v) > i .
Remark. Note that for any given index i ∈ {1, . . . , L − 1} and any time-step t ≤ T , an edge
(t)
e ∈ E (t) of the input graph appears at most once among the samples in Si (see Theorem 5.3).
(t)
(t)
Thus, the number of occurrences of an edge among the samples S1 , . . . , SL−1 is at most (L − 1).

5.5.5

Implementing the procedure in Figure 4 during a dense time-interval [t0 , t1 ]

Consider any dense time-interval [t0 , t1 ] ⊆ [1, T ], and fix any time-step t ∈ [t0 , t1 ]. The tth edge
insertion/deletion in the input graph might lead to some changes in the random subsets of edges
S1 , . . . , SL−1 ⊆ E. However, Theorem 5.3 implies that an edge insertion/deletion in G can lead to
at most two edge insertions/deletions in Si , for all i ∈ {1, . . . , L − 1}. Thus, due to the tth update in
the stream, there can be at most O(L) = Õ(1) insertions/deletions in the random sets S1 , . . . , SL−1
(see equation 6). After each such edge insertion/deletion in an Si , i ∈ {1, . . . , L − 1}, we update
the relevant data structures described in Section 5.5.4. Since an edge (u, v) ∈ Si can potentially
appear only in the lists Friendsi [x, j] with x ∈ {u, v} and j ∈ {1, . . . , L − 1} (see Section 5.5.4),
we reach the following conclusion:

30

• When an edge insertion/deletion in G leads to changes in the random edge sets Si , . . . , SL−1 ⊆
E, we can update the Friends and Dirty-Nodes lists from Section 5.5.4 in Õ(1) time.
After updating the edge sets S1 , . . . , SL−1 and the Friends and Dirty-Nodes lists, we run the
procedure described in Figure 4. Now, consider the ith iteration of the main For loop (Steps 05-10)
in Figure 4, for some index i ∈ {1, . . . , L − 1}. The purpose of this iteration is to construct the set
(t)
(t)
(t)
Zi+1 , based on the sets Zi and Si . Below, we state an alternate way of visualizing this iteration.
(t)

(t)

We scan through the list of nodes u with ℓ(u) = i and Du (Zi , Si ) > (1 − ǫ)2 αc log n. While
considering each such node u, we increment its level from i to (i+1). This takes care of the Steps (05)
(t)
(t)
and (07). Next, we scan through the list of nodes v with ℓ(v) > i and Dv (Zi , Si ) < (1+ǫ)2 c log n.
While considering any such node v at level ℓ(v) = jv > i (say), we decrement its level from jv to i.
This takes care of the Steps (06), (08) and (09).
Note that the nodes undergoing a level-change in the preceding paragraph are precisely the ones
that appear in the list Dirty-Nodes[i] just before the ith iteration of the main For loop. Thus,
we can implement Steps (05-10) as follows: Scan through the nodes y in Dirty-Nodes[i] one after
another. While considering any such node y, change its level as per Figure 4, and then update the
relevant data structures to reflect this change.
The next lemma states the space complexity of this procedure.
Lemma 5.9. Our algorithm in Figure 4 can be implemented in Õ(n) space.
o
n
(t)
, i ∈ [L−1]. Since
Proof. The amount of space needed is dominated by the number of edges in Si
(t)

|Si | ≤ s for each i ∈ [L − 1], the space complexity is (L − 1) · s = Õ(n) (see equations 6, 17).

The claim below bounds the time taken by a single iteration of the main For loop in Figure 4.
This will be crucially used to analyze the overall update time of our algorithm in Section 5.5.6.
Claim 5.10. Fix any time-step t ∈ [t0 , t1 ], and consider the ith iteration of the main For loop in
(t)
Figure 4 for some i ∈ {1, . . . , L − 1}. Consider two nodes u, v ∈ Zi such that:
• (a) the level of u is increased from i to (i + 1) in Step (07), and
• (b) the level of v is decreased to i in Steps (08–09).
Updating the relevant data structures for this step require
y = u (resp. v) in the former (resp. latter) case.

P

i′ >i O(1

(t)

(t)

+ Dy (Zi , Si′ )) time, where

Proof. Follows from the fact that we only need to update the lists Friendsi′ [x, j] where i′ > i,
(t)
(t)
x ∈ {y} ∪ Ny (Zi , Si′ ) and j ∈ {i, i + 1}.
5.5.6

The amortized update time of Dynamic-Stream during a dense time-interval

In this section, we bound the amortized update time of the subroutine Dynamic-stream during a
(t)
dense time-interval [t0 , t1 ]. Recall that the subroutine Dynamic-stream maintains an (α, dk , L)(t)
(t)
decomposition (V1 , . . . , VL ) of the input graph G(t) throughout the duration of such an interval.
To bound the amortized update time, we use a potential function B as defined in equation 24. Note
that the potential B is uniquely determined by the assignment of the nodes v ∈ V to the levels

31

{1, . . . , L} and by the contents of the random sets S1 , . . . , S(L−1) . For all nodes v ∈ V , we define:
Γi (v) = max(0, (1 − ǫ)2 αc log n − Dv (Zi , Si )) for all i ∈ {1, . . . , ℓ(v) − 1}

(21)

ℓ(v)−1

Φ(v) = (L/ǫ) ·

X

Γi (v)

(22)

i=1

For all u, v ∈ V , let f (u, v) = 1 if ℓ(u) = ℓ(v) and 0 otherwise. Also, let ruv = min(ℓ(u), ℓ(v)). For
all i ∈ {1, . . . , L − 1}, (u, v) ∈ Si , we define:
(
0
if ruv ≥ i;
,
(23)
Ψi (u, v) =
2 · (i − ruv ) + f (u, v) otherwise.
The potential B is defined as the sum of the potentials associated with all the nodes and edges.
(L−1)

B =

X

Φ(v) +

X X

Ψi (e)

(24)

i=1 e∈Si

v∈V

It might be instructive to contrast this potential function with the one used to analyze the dynamic
algorithm in Section 4.
Roadmap.

Our analysis works in three steps.

1. In Definition 5.11, we describe an event F. To understand the intuition behind this definition,
recall the discussion on the third technical challenge in Section 5.1.1: We have to overcome
(t)
the apparent obstacle that different levels of the (α, dk , L)-decomposition are constructed
using different subsets of randomly sampled edges. Intuitively, the event F guarantees that
the degrees of a node among these different subsets of edges are approximately the same with
high probability. This helps in extending the ideas from the potential function based analysis
in Section 4 to the current setting.
2. In Lemma 5.12, we show that the event F holds with high probability.
Lemma 5.12 appears in Section 5.5.7.

The proof of

3. Conditioned on the event F, we show that our algorithm has Õ(1) amortized update time
(see Lemma 5.13 and Corollary 5.14). The proof of Lemma 5.13 appears in Section 5.5.8.
Definition 5.11. Recall the procedure in Figure 4. For all levels i, i′ ∈ {1, . . . , L − 1} with i < i′ ,
(t)
and time-steps t ∈ [t0 , t1 ], we define an Fi,i′ as follows.
(t)

• The event Fi,i′ occurs iff the following conditions are satisfied.
–
–





(t)

(t)

(1−ǫ)4
(1+ǫ)2

(t)

(t)

(1+ǫ)4
(1−ǫ)2

Dv (Zi , Si′ ) ≥
Dv (Zi , Si′ ) ≤

Now, define the event F (t) =

T

(t)

· (αc log n) for all v ∈ Ai
(t)

· c log n for all v ∈ Bi
(t)

i,i′

Fi,i′ and the event F =

Lemma 5.12. The event F holds with high probability.
Lemma 5.13. Conditioned on the event F, we have:
32

, and

.
TT

t=T ′

F (t) .

• (a) 0 ≤ B = Õ(n) at each time-step t ∈ [t0 , t1 ].
• (b) Insertion/deletion of an edge in G (ignoring the call to the procedure in Figure 4) changes
the potential B by Õ(1).
• (c) For every constant amount of computation performed while implementing the procedure
in Figure 4, the potential B drops by Ω(1).
Corollary 5.14. With high probability, subroutine Dynamic-stream spends Õ(n + (t1 − t0 )) time
during the dense time-interval [t0 , t1 ]. So its amortized update time is Õ(1) with high probability.
Proof. Condition on the event F (which occurs with high probability by Lemma 5.12). At each
(t)
time-step t ∈ [1, T ], we maintain the random sets of edges {Si } as per Theorem 5.3. This takes
Õ(1) worst case update time. Further, a single edge insertion/deletion in the input graph leads to
(t)
at most two edge insertions/deletions in each of these sets {Si }, i ∈ {1, . . . , L − 1}.
(t)
(t)
Now, using the random sets {Si }, at each time-step t ∈ [t0 , t1 ] we maintain an (α, dk , L)decomposition of the input graph (see Lemma 5.8). Lemma 5.13 implies that with high probability,
this requires a total update time of Õ(n + (t1 − t0 )) for the entire duration of the interval [t0 , t1 ].
Finally, recall that either the dense time-interval spans Ω̃(n) time-steps, or it ends at time-step
T (see the discussion on the subroutine (P3) in Section 5.3). Hence, applying an argument similar to
the one used in Section 5.4 (see the discussions preceding equation 11), we conclude that with high
probability the subroutine Dynamic-stream spends Õ(T ) total time during the first T updates
in the dynamic stream. In other words, with high probability the subroutine Dynamic-stream
has an amortized update time of Õ(1).
5.5.7

Proof of Lemma 5.12

Fix any 1 ≤ i < i′ ≤ L − 1, and any time-step t ∈ [t0 , t1 ].
(t)

• Condition on an instantiation of the random set Zi . Note that this also determines the sets
(t)
(t)
Ai and Bi (see Figure 4).
(t)

– Let Wi

(t)

⊆ Zi

(t)

be the subset of nodes v with small degrees Dv (Zi , E (t) ). Specifically,


(1 − ǫ)2
(t)
(t)
(t)
(t)
(t)
Wi = v ∈ Zi : Dv (Zi , E ) <
· αdk
(25)
(1 + ǫ)2
(t)

(t)

The node set Wi is uniquely determined by the node set Zi (which we are conditioning
upon) and the edge set E (t) (which is given by the stream of updates in the input graph).
(t)

(t)

Now, consider any node v ∈ Wi . By Lemma 5.7, the contents of the random set Si
(t)
(t)
are independent of Zi . By Theorem 5.3, each edge (u, v) ∈ E (t) is included in Si with
probability (1 ± ǫ) · (s/m(t) ). Applying Linearity of expectation and equation 16, we get:
h
i
(t)
(t)
(t)
(t)
(26)
E Dv (Zi , Si ) ≤ (1 + ǫ) · (c log n/dk ) · Dv (Zi , E (t) )
≤

(1 − ǫ)2
· (αc log n)
(1 + ǫ)

(27)

Equation 27 follows from equations 25 and 26. Next, for each edge (u, v) ∈ E (t) incident
(t)
upon the node v, consider the random event that (u, v) ∈ Si . By Theorem 5.3, these
33

random events are negatively associated (see Section 2.4). Thus, applying Chernoff
(t)
bound on equation 27 and recalling the definition of Ai from Figure 4, we get:
i
h
i
h
(t)
(t)
(t)
(28)
Pr v ∈ Ai = Pr Dv (Zi , Si ) > (1 − ǫ)2 · (αc log n) ≤ 1/(poly n)
(t)

Applying a union bound on equation 28 over all the nodes in Wi , we get:
i
h
\ (t)
(t)
Ai 6= ∅ ≤ 1/(poly n)
Pr Wi
(t)

In other words, with high probability no node in Wi

(29)
(t)

belongs to the set Ai .

(t)

(t)

We will now bound the degrees of the nodes in Zi \ Wi with respect to the random
(t)
(t)
(t)
edge set Si′ . Towards this end, consider any node x ∈ Zi \ Wi . By Lemma 5.7,
(t)
(t)
the contents of the random set Si′ are independent of Zi . By Theorem 5.3, each edge
(t)
(u, v) ∈ E (t) is included in Si′ with probability (1 ± ǫ) · (s/m(t) ). Applying Linearity of
expectation and equations 16, 25 we get:
h
i
(t)
(t)
(t)
(t)
(30)
E Dx (Zi , Si′ ) ≥ (1 − ǫ) · (c log n/dk ) · Dv (Zi , E (t) )
≥

(1 − ǫ)3
· (αc log n)
(1 + ǫ)2

(31)

Equation 31 follows from equations 25 and 30. Next, for each edge (u, x) ∈ E (t) incident
(t)
upon the node x, consider the random event that (u, x) ∈ Si′ . By Theorem 5.3, these
random events are negatively associated (see Section 2.4). Thus, applying Chernoff
bound on equation 31, we get:


(1 − ǫ)4
(t)
(t)
Pr Dx (Zi , Si′ ) <
·
(αc
log
n)
≤ 1/(poly n)
(32)
(1 + ǫ)2
(t)

(t)

Now, taking an union bound on equation 32 over all the nodes in Zi \ Wi , we get:


(1 − ǫ)4
(t)
(t)
(t)
(t)
Pr Dx (Zi , Si′ ) <
· (αc log n) for some x ∈ Zi \ Wi
≤ 1/(poly n) (33)
(1 + ǫ)2
(t)

(t)

In other words, with high probability every node x ∈ Zi \ Wi has a high degree
(t)
(t)
Dx (Zi , Si′ ). Now, taking an union bound over equations 29 and 33, we conclude that:
(t)

(t)

With high probability, Dx (Zi , Si′ ) ≥

(1 − ǫ)4
(t)
· (αc log n) for every node x ∈ Ai .(34)
(1 + ǫ)2
(t)

Using a similar argument for the node set Bi , we can infer that:
(1 + ǫ)4
(t)
· (c log n) for every node x ∈ Bi . (35)
2
(1 − ǫ)
Taking an union bound over equations 34 and 35, we infer that:
(t)

(t)

With high probability, Dx (Zi , Si′ ) ≤
(t)

(t)

Given any instantiation of Zi , the event Fi,i′ occurs with high probability.
• From equation 36, we infer that:

(t)

The event Fi,i′ occurs with high probability.

(36)

(37)

The lemma follows by applying an union bound on equation 37 over all indices i, i′ ∈ {1, . . . , L − 1}
with i < i′ and time-steps t ∈ [t0 , t1 ].
34

5.5.8

Proof of Lemma 5.13

Part (a) and part (b) of the lemma hold independently of the event F. It is only during the proof
of part (c) that we have to condition of the event F.
Proof of part (a). Fix any time-step t ∈ [t0 , t1 ]. The proof follows from three facts.
1. We have 0 ≤ Φ(v) ≤ (L/ǫ) · L · (1 − ǫ)2 αc log n = Õ(1) for all v ∈ V .
(t)

2. We have 0 ≤ Ψi (u, v) ≤ 3L = Õ(1) for all i ∈ [L − 1], (u, v) ∈ Si .
(t)

3. We have |Si | ≤ s = Õ(n) for all i ∈ [L − 1]. This follows from equation 17.
Proof of part (b). By Theorem 5.3, insertion/deletion of an edge in G leads to at most two
(t)
(t)
insertions/deletions in each of the random sets S1 , . . . , SL−1 ⊆ E (t) . Since L = Õ(1) (see equa(t)

tion 6), it suffices to show that for a single edge insertion/deletion in any given Si , the potential
B changes by at most Õ(1) (ignoring the call to the procedure in Figure 4).
Towards this end, fix any i ∈ [L − 1], and suppose that a single edge (u, v) is inserted into
(t)
(resp. deleted from) Si . For each endpoint x ∈ {u, v}, this changes the potential Φ(x) by at most
O(L/ǫ). The potentials Φ(y) for all other nodes y ∈ V \ {u, v} remain unchanged. Additionally,
the potential Ψi (u, v) ∈ [0, 3L] is created (resp. destroyed). Thus, we infer that the absolute value
of the change in the overall potential B is at most O(3L + 2L/ǫ) = Õ(1).
Proof of part (c). Fix any time-step t ∈ [t0 , t1 ], and any iteration of the For loop in Figure 4
while processing the update in time-step t. Consider two possible events.
(t)

Case 1: A node v ∈ Zi

is promoted from level i to level (i + 1) in Step 07 of Figure 4.
(t)

This happens only if v ∈ Ai . Let C be the amount of computation performed during this step.
By Claim 5.10, we have:
(L−1)

C =

X

i′ =(i+1)



(t)
(t)
O 1 + Dv (Zi , Si′ )

(38)

Let ∆ be the net decrease in the overall potential B due to this step. We observe that:
(t)

(t)

1. Consider any i′ > i. For each edge (u, v) ∈ Si′ with u ∈ Zi , the potential Ψi′ (u, v) decreases
(t)
by at least one. For every other edge e ∈ Si′ , the potential Ψi′ (e) remains unchanged.
(t)

2. For each i′ ∈ [i] and each edge e ∈ Si′ , the potential Ψi′ (e) remains unchanged.
(t)

(t)

3. Since the node v is being promoted to level (i + 1), we have Dv (Zi , Si ) ≥ (1 − ǫ)2 αc log n.
Thus, the potential Φ(v) remains unchanged. For each node u 6= v, the potential Φ(u) can
only decrease (this holds since the degree Du (Zj , Sj ), for any level j, can only increase as
node v increases its level from i to i + 1).
Taking into account all these observations, we infer the following inequality.
(L−1)

∆ ≥

X

(t)

(t)

Dv (Zi , Si′ )

i′ =(i+1)

35

(39)

(t)

Since v ∈ Ai , and since we have conditioned on the event F (t) (see Definition 5.11), we get:
(t)

(t)

Dv (Zi , Si′ ) > 0

for all i′ ∈ [i + 1, L − 1].

(40)

Eq. (38), (39), (40) imply that the decrease in B is sufficient to pay for the computation performed.
(t)

Case 2: A node v ∈ Zi

is demoted from level j to level i in Steps (08-09) of Figure 4.
(t)

This can happen only if j > i and v ∈ Bi . Let C denote the amount of computation performed
during this step. By Claim 5.10, we have
(L−1)

X

C =

(t)

(t)

O(1 + Dv (Zi , Si′ ))

(41)

i′ =(i+1)
(t)

Let γ = (1 + ǫ)4 /(1 − ǫ)2 . Equation (42) holds since v ∈ Bi and since we conditioned on the
event F (see Definition 5.11). Equation (43) follows from equations (41), (42) and since γ, c are
constants.
(t)

(t)

Dv (Zi , Si′ ) ≤ γc log n for all i′ ∈ [i, L − 1]
C = O(L log n)

(42)
(43)

Let ∆ be the net decrease in the overall potential B due to this step. We observe that:
1. By eq. (42), the potential Φ(v) decreases by at least (j − i) · (L/ǫ) · ((1 − ǫ)2 α − γ) · (c log n).
2. For u ∈ V \ {v} and i′ ∈ [1, i] ∪ [j + 1, L − 1], the potential P
Γi′ (u) remains unchanged. This
observation, along with equation (42), implies that the sum u6=v Φ(u) increases by at most
P
(t)
(t)
(L/ǫ) · ji′ =(i+1) Dv (Zi , Si′ ) ≤ (j − i) · (L/ǫ) · (γc log n).
(t)

3. For every i′ ∈ [1, i], and e ∈ Si′ the potential Ψi′ (e) remains unchanged. Next, consider any
(t)
(t)
i′ ∈ [i + 1, L − 1]. For each edge (u, v) ∈ Si′ with u ∈ Zi , the potential Ψi′ (u, v) increases
(t)
Ψi′ (e)
by at most 3(j − i). For every other edge e ∈ Si′ , the potential P
P remains unchanged.
These observations, along with equation (42), imply that the sum i′ e∈Si′ Ψi′ (e) increases
P(L−1)
(t)
(t)
by at most i′ =(i+1) 3(j − i) · Dv (Zi , Si′ ) ≤ (j − i) · (3L) · (γc log n).

Taking into account all these observations, we get:

∆ ≥ (j − i)(L/ǫ)((1 − ǫ)2 α − γ)(c log n)

−(j − i)(L/ǫ)(γc log n) − (j − i)(3L)(γc log n)

= (j − i) · (L/ǫ) · ((1 − ǫ)2 α − 2γ − 3ǫγ) · (c log n)
≥ Lc log n

(44)

The last inequality holds since (j − i) ≥ 1 and α ≥ (ǫ + (2 + 3ǫ)γ)/(1 − ǫ)2 = 2 + Θ(ǫ), for some
sufficiently small constant ǫ ∈ (0, 1). From eq. (43) and (44), we conclude that the net decrease in
the overall potential B is sufficient to pay for the cost of the computation performed.
36

6

Extension to Directed Graphs

In this section, we extend our dynamic algorithm from Section 4 to directed graphs. The notion of
“density” of a directed graph was introduced by Kannan et al. [25]. We first recall their definition.
Y ⊆ V in a directed graph G = (V, E).
Definition 6.1. [25] Consider two subsets of nodes X,p
The “density” of this pair equals ρ(X, Y ) = |E(X, Y )|/ |X||Y |. Here, E(X, Y ) = {(u, v) : u ∈
X, v ∈ Y } is the set of edges going from X to Y . The value of the densest subgraph is given by
ρ(G) = maxX,Y ⊆V ρ(X, Y ). Note that we do not require the sets X and Y to be mutually disjoint.
Throughout this section, we denote the input graph by G = (V, E). In the beginning, the input
graph is empty, i.e., we have E = ∅. Subsequently, at each time-step, either a directed edge is
inserted into the graph, or an already existing edge is deleted from the graph. The set of nodes, on
the other hand, remains unchanged. Our goal is to maintain a good approximation of ρ(G) in this
dynamic setting. The main result is stated below.
Theorem 6.2. We can deterministically maintain a (8 + ǫ)-approximation to the value of the
densest subgraph of a directed graph G = (V, E). The algorithm requires Õ(m + n)-space, where m
(resp. n) denotes the number of nodes (resp. edges) in the graph. Furthermore, the algorithm has
an amortized update time of Õ(1) and a query time of O(1).
We devote the rest of Section 6 to the proof of Theorem 6.2. We first define the preliminary
concepts and notations in Section 6.1. Next, we extend the notion of an (α, d, L)-decomposition
to directed graphs in Section 6.2. In Section 6.3, we present our main algorithm. Finally, in
Section 6.4, we combine all these ingredients together and conclude the proof of Theorem 6.2.

6.1

Notations and Preliminaries

We first define the notion of a “derived graph”, which will be crucially used in our algorithm.
Definition 6.3. The “derived graph” G′ = (V ′ , E ′ ) of the input graph G = (V, E) is constructed as
follows. For each node v ∈ V , we create two nodes sv and tv . We define the node set V ′ = S ′ ∪ T ′ ,
where S ′ = {sv : v ∈ V } and T ′ = {tv : v ∈ V }. Next, for each directed edge (u, v) ∈ E, we create
the directed edge (su , tv ), and define the directed edge set E ′ = {(su , tv ) : (u, v) ∈ E}. Thus, in the
derived graph G′ = (V ′ , E ′ ), each node in S ′ (resp. T ′ ) has zero in-degree (resp. out-degree).
It is easy to check that the derived graph G′ = (V ′ , E ′ ) can be maintained in the dynamic
setting using O(m + n) space and O(1) update time: Fix the set of nodes V ′ = S ′ ∪ T ′ , and
whenever an edge (u, v) is inserted into (resp. deleted from) G = (V, E), insert (resp. delete) the
corresponding derived edge (su , tv ) in G′ . From now on, unless explicitly mentioned otherwise, our
main algorithm will work on the derived graph G′ = (V ′ , E ′ ). Before proceeding any further, we
introduce some notations that will be used throughout the rest of this section.
• Consider the derived graph G′ = (V ′ , E ′ ). Given any node s ∈ S ′ and any subset of nodes
T ⊆ T ′ , we let Ns (T ) = {t ∈ T : (s, t) ∈ E ′ } denote the set of neighbors of s among the
nodes in T . Furthermore, we let Ds (T ) = |Ns (T )| denote the degree of s among the nodes
in T . For a node t ∈ T ′ and a subset S ⊆ S ′ , the notations Nt (S) = {(s, t) ∈ E ′ : s ∈ S}
and Dt (S) = |Nt (S)| are defined analogously. Next, for any two subsets of nodes S ⊆ S ′
and T ⊆ T ′ , we let E ′ (S, T ) = {(s, t) ∈ E ′ : s ∈ S, t ∈ T } denote the set of edgespin the
derived graph that are going from S to T . We also define ρ′ (S, T ) = |E ′ (S, T )|/ |S||T |
for all S ⊆ S ′ , T ⊆ T ′ . Hence, from Definition 6.1, it follows that ρ′ (S, T ) = ρ(S, T ).
37

Accordingly, the value of the densest subgraph of the input graph G = (V, E) is given by
ρ(G) = maxS⊆S ′ ,T ⊆T ′ ρ′ (S, T ). We will denote the densest subgraph of G = (V, E) by the
pair (S ∗ , T ∗ ), where S ∗ ⊆ S ′ and T ∗ ⊆ T ′ . Thus, we have ρ′ (S ∗ , T ∗ ) = ρ(G). Finally, we
define the parameters λS ′ , λT ′ as follows.
p
p
(45)
λS ′ = |E(S ∗ , T ∗ )| · (1 − 1 − 1/|S ∗ |) and λT ′ = |E(S ∗ , T ∗ )| · (1 − 1 − 1/|T ∗ |).

We now state one crucial lemma that will be used in the analysis of our algorithm. This lemma
was proved by Khuller et al. [29]. For the sake of completeness, we state their proof below.

Lemma 6.4. [29] Consider the densest subgraph (S ∗ , T ∗ ) of the input graph G = (V, E). We have:
1. Ds (T ∗ ) ≥ λS ′ for all nodes s ∈ S ∗ , and Dt (S ∗ ) ≥ λT ′ for all nodes t ∈ T ∗ .
√
2. ρ(G)/2 ≤ λS ′ λT ′ ≤ ρ(G).

Proof.

1. For the sake of contradiction, suppose that there exists a node s ∈ S ∗ with Ds (T ∗ ) < λS ′ .
Then we can show that the density of the pair (S ∗ \ {s}, T ∗ ) is strictly larger than the density
of the pair (S ∗ , T ∗ ). Specifically, we can infer the following guarantee:
|E ′ (S ∗ , T ∗ )|
|E ′ (S ∗ , T ∗ )| − λS ′
=p
= ρ′ (S ∗ , T ∗ ) = ρ(G).
ρ′ (S ∗ \ {s}, T ∗ ) > p
(|S ∗ | − 1) · |T ∗ |
|S ∗ | · |T ∗ |

Since ρ(G) denotes the value of the densest subgraph of G, the above inequality leads to a
contradiction. Thus, we conclude that Ds (T ∗ ) ≥ λS ′ for all nodes s ∈ S ∗ . Using the same
line of reasoning, we can conclude that Dt (S ∗ ) ≥ λT ′ for all nodes t ∈ T ∗ .
2. From part I of the lemma, we have the following guarantee: Every node in S ∗ (resp. T ∗ )
has a degree of at least λS ′ (resp. λT ′ ) among the nodes in T ∗ (resp. S ∗ ). This implies that
|E ′ (S ∗ , T ∗ )| ≥ |S ∗ | · λS ′ and |E ′ (S ∗ , T ∗ ) ≥ |T ∗ | · λT ′ . Thus, we get:
p
p
|E ′ (S ∗ , T ∗ )| ≥ |S ∗ | · |T ∗ | · λS ′ · λT ′
(46)
p
′
∗
∗
′
∗
∗
Since ρ(G) = ρ (S , T ) = |E (S , T )|/ |S ∗ | · |T ∗ |, from equation 46 we conclude that:
|E ′ (S ∗ , T ∗ )| p
ρ(G) = p
(47)
≥ λS ′ · λT ′
|S ∗ | · |T ∗ |
Next, putting |S ∗ | = 1/ sin2 θ1 and |T ∗ | = 1/ sin2 θ2 , and recalling equation 45, we get:

 

p
p
|E ′ (S ∗ , T ∗ )|2
∗
∗
∗
∗
′
′
· (|S | · |T |) · 1 − 1 − 1/|S | · 1 − 1 − 1/|T |
λS · λT =
|S ∗ | · |T ∗ |
2 (1 − cos θ1 ) · (1 − cos θ2 )
= ρ′ (S ∗ , T ∗ ) ·
sin2 θ1 sin2 θ2
(ρ′ (S ∗ , T ∗ ))2
=
4 cos2 (θ1 /2) cos2 (θ2 /2)
(ρ′ (S ∗ , T ∗ ))2
(ρ(G))2
=
4
4
From equation 48 we conclude that:
p
λS ′ · λT ′ ≥ ρ(G)/2
≥

The part II of the lemma follows from equations 47 and 49.

38

(48)

(49)

6.2

(α, dS ′ , dT ′ , L)-Decomposition and Its Properties

We extend the concept of an (α, d, L)-decomposition (see Definition 2.5) to directed graphs. This
requires us to introduce one additional parameter in the definition, and we call the corresponding
entity an (α, dS ′ , dT ′ , L)-decomposition. Specifically, an (α, dS ′ , dT ′ , L)-decomposition of the derived
graph G′ = (V ′ , E ′ ), where V ′ = S ′ ∪ T ′ , is given by two laminar families of subsets of nodes
S ′ = S1 ⊇ S2 ⊇ · · · ⊇ SL and T ′ = T1 ⊇ T2 ⊇ · · · ⊇ TL . These subsets are iteratively constructed
as follows. First, we set S1 = S and T1 = T . Next, for each i ∈ {1, . . . , L − 1}, while constructing
the subsets Si+1 , Ti+1 from the subsets Si , Ti , we ensure the following conditions:
• Every node s ∈ Si with Ds (Ti ) > α · dS ′ is included in the subset Si+1 . On the other hand,
every node s ∈ Si with Ds (Ti ) < dS ′ is excluded from the subset Si+1 .
• Every node t ∈ Ti with Dt (Si ) > α · dT ′ is included in the subset Ti+1 . On the other hand,
every node t ∈ Ti with Dt (Si ) < dT ′ is excluded from the subset Ti+1 .
We are now ready to formally define the concept of an (α, dS ′ , dT ′ , L)-decomposition of G′ .
Definition 6.5. Fix any α ≥ 1, dS ′ , dT ′ ≥ 0, and any positive integer L. Consider a family of
subsets S ′ = S1 ⊇ · · · ⊇ SL and T ′ = T1 ⊇ · · · ⊇ TL . The tuples (S1 , . . . , SL ) and (T1 , . . . , TL ) form
an (α, dS ′ , dT ′ , L)-decomposition of the derived graph G′ iff for every i ∈ {1, . . . , L − 1}, we have:
1. Si+1 ⊇ {s ∈ Si : Ds (Ti ) > α · dS ′ } and Si+1 ∩ {s ∈ Si : Ds (Ti ) < dS ′ } = ∅.
2. Ti+1 ⊇ {t ∈ Ti : Dt (Si ) > α · dT ′ } and Ti+1 ∩ {t ∈ Ti : Dt (Si ) < dT ′ } = ∅.
Let Vi′ = (Si ∪ Ti ) \ (Si+1 ∪ Ti+1 ) for all i ∈ {1, . . . , L − 1}, and Vi′ = Si ∪ Ti for i = L. We say that
the nodes in Vi′ constitute the ith level of this decomposition. We also denote the level of a node
v ∈ V ′ by ℓ(v). Thus, we have ℓ(v) = i whenever v ∈ Vi′ , and the set of nodes V ′ is partitioned into
L subsets V1′ , . . . , VL′ .
Theorem 6.6 and Corollary 6.7 will play the main role in the rest of this section. Roughly
speaking, they are generalizations of Theorem 2.6 and Corollary 2.7 from Section 2.2, and they
state that we can use the (α, dS ′ , dT ′ , L)-decomposition to 4α(1 + ǫ)3/2 -approximate of the value of
the densest subgraph of G = (V, E). All we need to do is to set L = O(log n/ǫ) and try different
values of dS ′ , dT ′ in powers of (1 + ǫ).
Theorem 6.6. Fix any α ≥ 1, dS ′ , dT ′ ≥ 0, ǫ ∈ (0, 1), and L ← 2 · (2 + ⌈log(1+ǫ) n⌉). Let
(S1 , . . . , SL ), (T1 , . . . , TL ) be an (α, dS ′ , dT ′ , L)-decomposition of the derived graph G′ = (V ′ , E ′ ) as
per Definition 6.5. Then the following conditions are satisfied.
1. If dS ′ dT ′ > 4(1+ ǫ)λS ′ λT ′ , then VL′ = ∅ (i.e., the topmost level of the decomposition is empty).
2. If dS ′ < λS ′ /α and dT ′ < λT ′ /α, then VL′ 6= ∅ (i.e., the topmost level is nonempty).
Proof.
1. For any level k ∈ {2, . . . , L}. Definition 6.5 states that for every node s ∈ Sk , we have
Ds (Tk−1 ) > dS ′ . We thus get a lower bound on the number edges going from Sk to Tk−1 .
|E ′ (Sk , Tk−1 )| ≥ |Sk | · dS ′

39

(50)

√
′
Recall that by p
Lemma 6.4, we have ρ(G)
≤
2
·
λp
S ′ λT ′ . This implies that ρ (Sk , Tk−1 ) =
√
|E ′ (Sk , Tk−1 )|/ |Sk ||Tk−1 | ≤ ρ(G) ≤ 2 · λS ′ λT ′ ≤ dS ′ dT ′ /(1 + ǫ). Hence, we get:
s
|Sk | · |Tk−1 | · |dS ′ | · |dT ′ |
(51)
|E ′ (Sk , Tk−1 )| ≤
(1 + ǫ)
From equations 50 and 51, we get:
|Sk | · dS ′ ≤ |Tk−1 | · dT ′ /(1 + ǫ)

(52)

Replacing S by T in the above argument, we can analogously show that:
|Tk | · dT ′ ≤ |Sk−1 | · dS ′ /(1 + ǫ)

(53)

Now, we consider two possible cases.
• If |Sk−1 | · dS ′ ≥ |Tk−1 | · dT ′ , then equation 52 implies that |Sk | ≤ |Sk−1 |/(1 + ǫ).

• Else if |Sk−1 | · dS ′ < |Tk−1 | · dT ′ , then equation 53 implies that |Tk | < |Tk−1 |/(1 + ǫ).

In other words, when going from level k − 1 to level k, either the size of S or the size of T
reduces by a factor of (1 + ǫ). Since |S1 | = |T1 | = n and L = 2 · (2 + ⌈log(1+ǫ) n⌉), after L
levels both the sets S and T are empty. We thus have SL = TL = ∅.
2. Consider the densest subgraph of the input graph G = (V, E), given by the pair (S ∗ , T ∗ )
where S ∗ ⊆ S ′ and T ∗ ⊆ T ′ . Lemma 6.4 states that each node s ∈ S ∗ (resp. t ∈ T ∗ ) has
out-degree (resp. in-degree) at least λS ′ (resp. λT ′ ) with respect to the nodes in T ∗ (resp.
S ∗ ). Since λS ′ > α · dS ′ and λT ′ > α · dT ′ , Definition 6.5 implies the following guarantee:
• If S ∗ ⊆ Si , T ∗ ⊆ Ti for some i ∈ {1, . . . , L − 1}, then we also have S ∗ ⊆ Si+1 , T ∗ ⊆ Ti+1 .
Since S1 = S ′ , T1 = T ′ , we have S ∗ ⊆ S1 and T ∗ ⊆ T1 . Hence, applying the above guarantee
in an inductive fashion, we conclude that S ∗ ⊆ SL and T ∗ ⊆ TL . Thus, VL′ = SL ∪ TL 6= ∅.
Corollary 6.7. As in Theorem 6.6, fix any α ≥ 1, ǫ ∈ (0, 1) and L = 2 · (2 + ⌈log(1+ǫ) n⌉).
p
Define λ∗ = 1 − 1 − 1/n. Discretize the range [λ∗ /(α(1 + ǫ)), n2 ] in powers of (1 + ǫ), by letting qk = (1 + ǫ)k−1 λ∗ /α for every integer k ≥ 0. Let K be the smallest integer k for which
qk ≥ n2 . For all dS ′ , dT ′ ∈ {d0 , . . . , dK }, construct an (α, dS ′ , dT ′ , L)-decomposition of G′ as per
Definition 6.5, and let VL′ (dS ′ , dT ′ ) denote the set of nodes at level L of such a decomposition. Let
P = {(dS ′ , dT ′ ) : dS ′ , dT ′ ∈ {0, . . . , K}, VL′ (dS ′ , dT ′ ) 6= ∅} denote the set of those (dS ′ , dT ′ ) pairs for
which the topmost level of the decomposition is non-empty. If P = ∅, then define γ = 0. Else define
γ = max(dS ′ ,dT ′ )∈P {dS ′ · dT ′ }. Then we have:
2·

p

(1 + ǫ) · ρ(G) ≥

√

γ≥

ρ(G)
.
2 · α · (1 + ǫ)

Proof. If the derived graph is empty, i.e., if E ′ = ∅, then we have E = ∅, P = ∅, γ = 0, and
ρ(G) = 0. Thus, in this case the corollary is trivially true.
For the remainder of the proof, we assume that E ′ 6= ∅. Here, it is easy to see that P 6= ∅:
simply consider the (α, dS ′ , dT ′ , L)-decomposition with dS ′ = dT ′ = q0 < 1. In this decomposition,
every node in G′ with nonzero degree will be promoted to the topmost level VL′ (dS ′ , dT ′ ).
40

Accordingly, for the rest of the proof, we fix a (dS ′ , dT ′ )-pair in P for which dS ′ · dT ′ = γ. Let
this pair be identified as (d∗S ′ , d∗T ′ ). Since (d∗S ′ , d∗T ′ ) ∈ P , we infer that VL′ (d∗S ′ , d∗T ′ ) 6= ∅. Hence, by
the first part of Theorem 6.6, we must have:
γ = d∗S ′ · d∗T ′ ≤ 4(1 + ǫ) · λS ′ · λT ′ .

(54)

Next, define dˆS ′ (resp. dˆT ′ ) to be the maximum value of dS ′ (resp. dT ′ ) which is less than the
threshold λS ′ /α (resp. λT ′ /α). Note that since E ′ 6= ∅, we have λ∗ ≤ λS ′ , λT ′ < n2 . Thus, we are
guaranteed the existence of such a pair (dˆS ′ , dˆT ′ ).
dˆS ′ =

max

k∈{0,...,K} : qk <λS ′ /α

{qk } and dˆT ′ =

max

{qk }

k∈{0,...,K} : qk <λT ′ /α

(55)

Next, note that q0 < λ∗ /α and qK ≥ n2 . Since the consecutive qk values are within a factor of
(1 + ǫ) from each other, equation 55 gives us:
λS ′ · λT ′
· (1 + ǫ)2

(56)

γ = d∗S ′ · d∗T ′ ≥ dˆS ′ · dˆT ′

(57)

dˆS ′ · dˆT ′ ≥

α2

Since dˆS ′ < λS ′ /α and dˆT ′ < λT ′ /α, Theorem 6.6 (part II) implies that VL′ (dˆS ′ , dˆT ′ ) 6= ∅. Thus, we
have (dˆS ′ , dˆT ′ ) ∈ P . Since (d∗S ′ , d∗T ′ ) ∈ P maximizes the product of its two components, we get:
From equations 54, 56 and 57, we infer that:
λS ′ · λT ′
(58)
≤ γ ≤ 4(1 + ǫ) · λS ′ · λT ′
· (1 + ǫ)2
√
By the second part of Lemma 6.4, we have: ρ(G)/2 ≤ λS ′ λT ′ ≤ ρ(G). Combining this observation
with equation 58, we get:
p
ρ(G)
√
(59)
≤ γ ≤ 2 · (1 + ǫ) · ρ(G)
2α(1 + ǫ)
This concludes the proof of the corollary.
α2

6.3

The Algorithm for Maintaining an (α, dS ′ , dT ′ , L)-Decomposition

Throughout this section, we fix the values of dS ′ , dT ′ , L. Furthermore, we fix an α ≥ 2 + ǫ.
We describe an algorithm for maintaining an (α, dS ′ , dT ′ , L)-decomposition of the derived graph
G′ = (V ′ , E ′ ) in a dynamic setting (see Definition 6.3). We assume that the input graph G = (V, E)
is empty in the beginning, and hence, at that instant we also have E ′ = ∅. Subsequently, at each
time-step, a directed edge (u, v) is inserted into (resp. deleted from) the graph G = (V, E), and
accordingly, the edge (su , tv ) is inserted into (resp. deleted from) the derived graph G′ = (V ′ , E ′ ).
Our main result is stated below.
Theorem 6.8. For every polynomially bounded α ≥ 2 + 3ǫ, we can deterministically maintain an
(α, dS ′ , dT ′ , L)-decomposition of the derived graph G′ = (V ′ , E ′ ). Starting from an empty graph,
we can handle a sequence of t update operations (edge insertions/deletions) in total time O(tL/ǫ).
Thus, we get an amortized update time of O(L/ǫ). The space complexity of the data structure at
a given time-step is O(n + m), where m = |E ′ | denotes the number of edges in the derived graph
at that time-step, and n = |V ′ | denotes the number of nodes in the derived graph (which does not
change over time). Note that |V | = 2n and |E| = m, where G = (V, E) is the input graph.
The proof of Theorem 6.8 is very similar to the proof of Theorem 4.2 from Section 4.1. Nevertheless, for the sake of completeness, we highlight the main parts of the algorithm and its analysis.
41

Data Structures. Recall the concept of the level of a node from Definition 6.5. We now separately describe the data structures associated with the nodes in S ′ and T ′ .
• Every node s ∈ S ′ maintains L lists Friendsi [s], for i ∈ {1, . . . , L}. For i < ℓ(s), the list
Friendsi [s] consists of the neighbors of s that are at level i: these are nodes belonging to
the set Ns (Vi′ ∩ Ti ). For i = ℓ(s), the set Friendsi [s] consists of the neighbors of s that
are at level i or above: these are the nodes belonging to the set Ns (Ti ). For i > ℓ(s), the
list Friendsi [s] is empty. Each list is stored in a doubly linked list together with its size,
Counti [s]. Using appropriate pointers, we can insert or delete a given node to or from a
concerned list in constant time. The counter Level[s] keeps track of the level of the node s.
• Analogously, every node t ∈ T ′ maintains L lists Friendsi [t], for i ∈ {1, . . . , L}. For i < ℓ(t),
the list Friendsi [t] consists of the neighbors of t that are at level i: these are nodes belonging
to the set Nt (Vi′ ∩ Si ). For i = ℓ(t), the set Friendsi [t] consists of the neighbors of t that
are at level i or above: these are the nodes belonging to the set Nt (Si ). For i > ℓ(t), the
list Friendsi [t] is empty. Each list is stored in a doubly linked list together with its size,
Counti [t]. Using appropriate pointers, we can insert or delete a given node to or from a
concerned list in constant time. The counter Level[t] keeps track of the level of the node t.
The Algorithm. If a node violates one of the conditions of an (α, dS ′ , dT ′ , L)-decomposition (see
Definition 6.5), then we call the node “dirty”, else the node is called “clean”. Specifically, consider
two possible cases depending on the type of the node.
• A node s ∈ S ′ at level ℓ(s) = i is dirty iff either (a) i < L and Ds (Ti ) > α · dS ′ , or (b) i > 1
and Ds (Ti−1 ) < dS ′ .
• A node t ∈ T ′ at level ℓ(t) = i is dirty iff either (a) i < L and Dt (Si ) > α · dT ′ , or (b) i > 1
and Dt (Si−1 ) < dT ′ .
Initially, the derived graph G′ = (V ′ , E ′ ) is empty, every node is at level 1, and every node is
clean. When an edge (s, t), s ∈ S ′ , t ∈ T ′ , is inserted/deleted in the derived graph G′ , we first
update the Friends lists of s and t by adding or removing that edge in constant time. Next we
check whether s or t becomes dirty due to this edge insertion/deletion. If yes, then we run the
RECOVER-DIRECTED() procedure described in Figure 5. Note that a single iteration of the
While loop (Steps 01-15) may change the status of some more nodes from clean to dirty (or vice
versa). If and when the procedure terminates, however, every node is clean by definition.
Space complexity. Since each edge in G′ = (V ′ , E ′ ) appears in two linked lists (corresponding
to each of its endpoints), the space complexity of the data structure is O(n + m).
Analysis of the Update Time. Handling each edge insertion/deletion takes constant time plus
the time for the RECOVER-DIRECTED() procedure. We show below that the total time spent in
procedure RECOVER-DIRECTED() during t update operations is O(tL/ǫ).
Potential Function. To determine the amortized update time we use a potential function B
that depends on the state of the (α, dS ′ , dT ′ , L)-decomposition. For any two nodes s ∈ S ′ , t ∈ T ′ ,
let f (s, t) = 1 if l(s) = l(t) and 0 otherwise. We define B, the node potentials Φ(x) (for each
x ∈ V ′ = S ′ ∪ T ′ ), and the edge potentials Ψ(s, t) (for each (s, t) ∈ E ′ ) as follows.

42

01.
02.
03.
04.
05.
06.
07.
08.
09.
10.
11.
12.
13.
14.
15.

While there exists a dirty node y ∈ V ′ = S ′ ∪ T ′ :
If y ∈ S ′ , Then
If Dy (Tℓ(y) ) > α · dS ′ and ℓ(y) < L, Then
Increment the level of s by setting ℓ(y) ← ℓ(y) + 1.
Update the relevant data structures to reflect this change.
Else if Dy (Tℓ(y)−1 ) < dS ′ and ℓ(y) > 1, Then
Decrement the level of y by setting ℓ(y) ← ℓ(y) − 1.
Update the relevant data structures to reflect this change.
Else if y ∈ T ′ , Then
If Dy (Sℓ(y) ) > α · dT ′ and ℓ(y) < L, Then
Increment the level of s by setting ℓ(y) ← ℓ(y) + 1.
Update the relevant data structures to reflect this change.
Else if Dy (Sℓ(y)−1 ) < dT ′ and ℓ(y) > 1, Then
Decrement the level of y by setting ℓ(y) ← ℓ(y) − 1.
Update the relevant data structures to reflect this change.
Figure 5: RECOVER-DIRECTED().

B =

X

Φ(x) +

x∈S ′ ∪T ′

X

Ψ(s, t)

(60)

(s,t)∈E ′

  ℓ(s)−1
X
1
·
max(0, α · dS ′ − Ds (Ti ))
Φ(s) =
ǫ

for all nodes s ∈ S ′

(61)

for all nodes t ∈ T ′

(62)

Ψ(s, t) = 2 · (L − min(ℓ(s), ℓ(t))) + f (s, t) for all edges (s, t) ∈ E ′

(63)

i=1

  ℓ(t)−1
X
1
·
max(0, α · dT ′ − Dt (Si ))
Φ(t) =
ǫ
i=1

It is easy to check that all these potentials are nonnegative, and that they are uniquely defined
by the (α, dS ′ , dL′ , L)-decomposition under consideration. Now, mimicking the potential function
based analysis from Section 4.1, we can infer the following facts.
• (F1) In the beginning, when the derived graph G′ = (V ′ , E ′ ) is empty, we have B = 0.
Subsequently, the potential B remains always nonnegative.
• (F2) Insertion/deletion of an edge in the derived graph G′ = (V ′ , E ′ ) increases the potential
B by at most 3L/ǫ.
• To analyze the amortized running time of the RECOVER-DIRECTED() procedure, we have
the following claims.
– (F3) Consider a single iteration of the While loop in Figure 5 where a node s ∈ S ′ with
ℓ(s) = i changes (increments or decrements) its level by one. This takes O(1 + Ds (Ti ))
time. On the other hand, the net drop in the overall potential B due to the same iteration
of the While loop is Ω(1 + Ds (Ti )), provided α ≥ 2 + 3ǫ.

– (F4) Consider a single iteration of the While loop in Figure 5 where a node t ∈ T ′ with
ℓ(t) = i changes (increments or decrements) its level by one. This takes O(1 + Dt (Si ))
43

time. On the other hand, the net drop in the overall potential B due to the same iteration
of the While loop is Ω(1 + Dt (Si )), provided α ≥ 2 + 3ǫ.
Facts (F1) – (F4) imply that the RECOVER-DIRECTED() procedure takes a total time of O(tL/ǫ)
to handling the first t edge insertions/deletions in the derived graph G′ = (V ′ , E ′ ). This gives an
amortized update time of O(L/ǫ) for our algorithm and concludes the proof of Theorem 6.8.

6.4

Wrapping Up: Proof of Theorem 6.2

We fix a sufficiently small constant ǫ ∈ (0, 1) and set α = 2 + 3ǫ, L = 2 · (2 + ⌈log(1+ǫ) n⌉), and
√
λ∗ = 1 − 1/ n. Next, as in Corollary 6.7, we discretize the range [λ∗ /(α(1 + ǫ)), n2 ] by setting
qk = (1+ǫ)k−1 ·λ∗ /α for every integer k ≥ 0. We then define K to be the smallest integer k for which
qk ≥ n2 . Next, we maintain an (α, dS ′ , dT ′ , L)-decomposition of the derived graph G′ = (V ′ , E ′ ) for
every dS ′ , dT ′ ∈ {d0 , . . . , dK }. By Theorem 6.8, maintaining each of these decompositions requires
O(m + n) space and O(L/ǫ) amortized update time. Hence, the total space requirement of our
scheme is O(K 2 (m + n)) = Õ(m + n) and the total amortized update time is O(K 2 L/ǫ) = Õ(1).
We also maintain the value of γ as defined in Corollary 6.7. Since there are O(K 2 ) decompositions,
maintaining
the value of γ also requires O(K 2 ) = Õ(1) update time. By Corollary 6.7, the quantity
√
√
γ/(2 1 + ǫ) gives a 4α · (1 + ǫ)3/2 = 8 · (1 + O(ǫ))-approximation to the value of the densest
subgraph ρ(G). This concludes the proof of Theorem 6.2.

7

Sublinear-Time Algorithm

In this section, we focus on sublinear time algorithms for the approximate densest subgraph problem. Our main results are summarized in Theorems 7.1 and 7.3.
If we assume that an algorithm has to read all of its input, then no sublinear (in the input
size) time algorithm is possible. However, if we assume that the input is given by an oracle that
gives efficient access to the input, then sublinear time algorithms might exist. We present in the
following such an oracle that allows us to turn our algorithm from Section 3 into a sublinear time
algorithm. Specifically, we will give an Õ(n) time algorithm that requires Õ(n) oracle queries and
space. Afterwards we will also show that with this oracle no further assymptotic improvement is
possible.
Oracle model. We first present the oracle model for the input graph. It is a standard representation that is, e.g., assumed in the sublinear time algorithms of [10, 19] and is called incident-list
model. In this representation, we allow two types of accesses to the input graph (called oracle
queries): (1) the degree query which asks for the degree of some node v, and (2) the neighbor query
which asks for the ith neighbor of v (i.e. the ith element in the incidence list corresponding to the
neighbors of v). See, e.g., [12, 21, 22, 36, 38, 39] for further surveys.
Upper Bound. In Section 3, we showed how to compute a (2 + ǫ)-approximate solution to the
densest subgraph problem using only Õ(n) edges sampled uniformly at random. In the above oracle
model, sampling an edge can be done using one neighbor query. Thus, the algorithm needs only
Õ(n) queries. After the sampling is completed we can process the collection of sampled edges using
Õ(n) time and space, as in the proof of Theorem 3.1, simply by computing the (1 + ǫ, d, Õ(1))decomposition for different Õ(1) values of d, to get the desired (2 + ǫ)-approximate solution. This
leads to the following theorem.

44

Theorem 7.1. There is a sub-linear time algorithm for computing a (2+ǫ)-approximate solution to
the densest subgraph problem in the incidence-list model. The algorithm makes Õ(n) oracle queries,
and requires Õ(n) time and Õ(n) space.
Lower Bound. We adapt the proof of [6, Lemma 7] to show that for any λ ≥ 3/2, a λapproximation algorithm needs to make Ω(n/(λ2 poly log(n))) oracle queries. Consider the following
communication complexity problem “P1”:
• There are k ≥ 2 players, denoted by p1 , . . . , pk and an n-node input graph G consisting of ℓ
disjoint subgraphs, denoted by G1 , . . . , Gℓ . Each Gi has k nodes, denoted by {ui,1 , . . . , ui,k }
(thus n = kℓ). Further each subgraph is either a star or a clique. For any node ui,j in Gi , if its
degree is more than one then player pj knows about all edges incident to ui,j . In other words,
pj knows about edges incident to nodes with degree more than one among u1,j , u2,j , . . . , uℓ,j .
The players want to distinguish between the case where there is a clique (thus the densest
subgraph has density at least (k−1)/2) and when there is no clique (thus the densest subgraph
has density at most 1). Their communication protocol is in the blackboard model, where in
each round a player can write a message on the backboard, which will be seen by all other
players, and the communcation complexity is the number of bits written to the board. Using
a reduction from the multi-party set disjointness problem, the papers [6, 8] showed that this
problem require Ω̃(ℓ/k) = Ω̃(n/k2 ) communication bits.
Lemma 7.2. If there is a sublinear-time algorithm with q oracle queries for the problem P1 defined
above, then the problem P1 can also be solved using Õ(q) communication bits.
Proof. Let A be such algorithm. Player p1 simulates A by answering each query of A using Õ(1)
communication bits, as follows. If A makes a degree query on node uij , player p1 will ask for an
answer from player pj : either pj knows all edges incident to uij (in which case the degree of uij
is k) or the degree of uij is one. If A asks for the tth neighbor of node uij , player p1 asks for this
from player pj . If player pj does not know the answer, then we know that the degree of uij is one
and Gi is a star. In this case, player p1 writes on a blackboard asking for the unique node uij ′ in
Gi whose degree is more than one. Then, the only edge incident to uij is uij uij ′ . This edge can be
used to answer the query.
Note that any ((k − 1)/2 − ǫ)-approximation algorithm for the densest subgraph problem solves
problem P1. Thus, the above lemma implies that any ((k − 1)/2 − ǫ)-approximation algorithm
requires Ω̃(n/k) queries. By considering any k ≥ 4, we get the following theorem.
Theorem 7.3. In the incidence-list model, for any λ ≥ 3/2 and any ǫ > 0, any λ−ǫ-approximation
algorithm for the densest subgraph problem needs to make Ω̃(n/λ2 ) queries.

8

Distributed Streams

In the distributed streaming model (see, e.g., [11]), there are k sites receiving different sequences
of edge insertions (without any deletion), and these sites must coordinate with the coordinator.
The objective is to minimize the communication between the sites and the coordinator in order
to maintain the densest subgraph. We sample Õ(n) edges (without replacement) as a sketch by
using the sampling algorithm of Cormode et al. [11]: their algorithm can sample Õ(n) edges using
Õ(k + n) bits of communication, whereas the coordinator needs Õ(n) space and each site needs
Õ(1) space. The coordinator can then use this sketch to compute a (2 + ǫ)-approximate solution.

45

Theorem 8.1. In the distributed streaming setting with k sites [11], we can compute a (2 + ǫ)approximate solution to the densest subgraph problem using Õ(k + n) bits of communication. The
coordinator needs Õ(n) space and each site needs Õ(1) space.

9

Open problems

An obvious question is whether the (4 + ǫ) approximation ratio provided by our algorithm is tight.
In particular, it will be interesting if one can improve the approximation ratio to (2 + ǫ) to match
the case where an update time is not a concern. Getting this approximation ratio even with larger
space complexity is still interesting. (Epasto et al. [14] almost achieved this except that they have
to assume that the deletions happen uniformly at random.) It is equally interesting to show a
hardness result. Currently, there is only a hardness result for maintaining the optimal solution [23].
It will be interesting to show a hardness result for approximation algorithms. Another interesting
question is whether a similar result to ours can be achieved with polylogarithmic worst-case update
time. Finally, a more general question is whether one can obtain space- and time-efficient fullydynamic algorithm like ours for other fundamental graph problems, e.g. maximum matching and
single-source shortest paths.

References
[1] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear
measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 459–467, 2012. 1,
3
[2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium
on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages
5–14, 2012. 1, 4
[3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph
streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and
Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop,
RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 1–10, 2013. 1
[4] Albert Angel, Nick Koudas, Nikos Sarkas, and Divesh Srivastava. Dense subgraph maintenance
under streaming edge weight updates for real-time story identification. PVLDB, 5(6):574–585,
2012. 1
[5] Bahman Bahmani, Ashish Goel, and Kamesh Munagala. Efficient primal-dual algorithms for
MapReduce. In Algorithms and Models for the Web Graph - 11th International Workshop,
WAW 2014, Proceedings, 2014. 4
[6] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and
mapreduce. PVLDB, 5(5):454–465, 2012. 1, 4, 5, 45
[7] Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representation of sparse graphs. In
Algorithms and Data Structures, 6th International Workshop, WADS ’99, Vancouver, British
Columbia, Canada, August 11-14, 1999, Proceedings, pages 342–351, 1999. 4
46

[8] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the
multi-party communication complexity of set disjointness. In 18th Annual IEEE Conference
on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages
107–117, 2003. 45
[9] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In
Klaus Jansen and Samir Khuller, editors, APPROX, volume 1913 of Lecture Notes in Computer
Science, pages 84–95. Springer, 2000. 1, 4
[10] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., 34(6):1370–1379, 2005. 4, 44
[11] Graham Cormode, S. Muthukrishnan, Ke Yi, and Qin Zhang. Optimal sampling from distributed streams. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis,
Indiana, USA, pages 77–86, 2010. 4, 45, 46
[12] Artur Czumaj and Christian Sohler. Sublinear-time algorithms. In Property Testing, pages
41–64, 2010. 44
[13] Yon Dourisboure, Filippo Geraci, and Marco Pellegrini. Extraction and classification of dense
communities in the web. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider,
and Prashant J. Shenoy, editors, WWW, pages 461–470. ACM, 2007. 1
[14] Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. Efficient densest subgraph computation
in evolving graphs. In Proceedings of the 24th International Conference on World Wide Web,
WWW 2015, Florence, Italy, May 18-22, 2015, pages 300–310, 2015. 4, 46
[15] Paul Erdös, Arthur H Stone, et al. On the structure of linear graphs. Bull. Amer. Math. Soc,
52:1087–1091, 1946. 5
[16] Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. Applications of
uniform sampling: Densest subgraph and beyond. CoRR, abs/1506.04505, 2015. 4
[17] Shimon Even and Yossi Shiloach. An On-Line Edge-Deletion Problem. Journal of the ACM,
28(1):1–4, 1981. 1
[18] David Gibson, Ravi Kumar, and Andrew Tomkins. Discovering large dense subgraphs in
massive graphs. In VLDB, pages 721–732, 2005. 1
[19] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Perfect matchings in o(nlog n) time
in regular bipartite graphs. SIAM J. Comput., 42(3):1392–1404, 2013. Announced at STOC
2010. 4, 44
[20] A. V. Goldberg. Finding a maximum density subgraph. Technical report, Berkeley, CA, USA,
1984. 1
[21] Oded Goldreich. A brief introduction to property testing. In Studies in Complexity and
Cryptography, pages 465–469. 2011. 44
[22] Oded Goldreich. Introduction to testing graph properties. In Studies in Complexity and
Cryptography, pages 470–506. 2011. 44

47

[23] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on
Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21–30, 2015.
46
[24] Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for lp samplers, finding
duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMODSIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16,
2011, Athens, Greece, pages 49–58, 2011. 10, 11
[25] Ravi Kannan and V. Vinay. Analyzing the structure of large graphs. Technical report, 1999.
37
[26] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.
Single pass spectral sparsification in dynamic streams. In 55th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2014, 28-22 October, 2014, Philadelphia, PA, USA,
pages 561–570, 2014. 1
[27] Michael Kapralov and David P. Woodruff. Spanners and sparsifiers in dynamic streams. In
ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July
15-18, 2014, pages 272–281, 2014. 1
[28] Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages
1131–1142, 2013. 1
[29] Samir Khuller and Barna Saha. On finding dense subgraphs. In Automata, Languages and
Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009,
Proceedings, Part I, pages 597–608, 2009. 38
[30] Eugene Lawler. Combinatorial Optimization: Networks and Matroids. Saunders College Publishing, Fort Worth, 1976. 1
[31] Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu C. Aggarwal. A survey of algorithms for
dense subgraph discovery. In Managing and Mining Graph Data, pages 303–336. 2010. 1
[32] David W Matula. A min-max theorem for graphs with application to graph coloring. In
SIAM REVIEW, volume 10, page 481. SIAM PUBLICATIONS 3600 UNIV CITY SCIENCE
CENTER, PHILADELPHIA, PA 19104-2688, 1968. 5
[33] Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. Densest subgraph in
dynamic graph streams. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II,
pages 472–482, 2015. 4
[34] Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos E. Tsourakakis, and
Shen Chen Xu. Scalable large near-clique detection in large-scale networks via sampling. In
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and
Data Mining, pages 815–824. ACM, 2015. 4

48

[35] J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput.
Sci., 12:315–323, 1980. Announced at FOCS’78. 1
[36] Krzysztof Onak. Sublinear graph approximation algorithms. In Property Testing, pages 158–
166, 2010. 44
[37] Anna Pagh and Rasmus Pagh. Uniform hashing in constant time and optimal space. SIAM
J. Comput., 38(1):85–96, 2008. 10, 22
[38] Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends
in Theoretical Computer Science, 5(2):73–205, 2009. 44
[39] Ronitt Rubinfeld and Asaf Shapira. Sublinear time algorithms. SIAM J. Discrete Math.,
25(4):1562–1588, 2011. 44
[40] Ahmet Erdem Sariyüce, Bugra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V.
Çatalyürek. Streaming algorithms for k-core decomposition. PVLDB, 6(6):433–444, 2013. 5
[41] George Szekeres and Herbert S Wilf. An inequality for the chromatic number of a graph.
Journal of Combinatorial Theory, 4(1):1–3, 1968. 5
[42] Lei Tang and Huan Liu. Graph mining applications to social network analysis. In Managing
and Mining Graph Data, pages 487–513. 2010. 1
[43] Charalampos Tsourakakis. The k-clique densest subgraph problem. In Proceedings of the 24th
International Conference on World Wide Web, pages 1122–1132. International World Wide
Web Conferences Steering Committee, 2015. 1

49

