The Sparse Awakens: Streaming Algorithms for Matching Size
Estimation in Sparse Graphs

arXiv:1608.03118v2 [cs.DS] 14 Nov 2016

Graham Cormode∗

Hossein Jowhari†

Morteza Monemizadeh‡

S. Muthukrishnan §

November 15, 2016

Abstract
Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one
that has attracted extensive study over a range of different computational models. We present improved
streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity)
graphs.
• (Insert-Only Streams) We present a one-pass algorithm that takes O(c log2 n) space and approximates the size of the maximum matching in graphs with arboricity c within a factor of O(c). This
improves significantly upon the state-of-the-art Õ(cn2/3 )-space streaming algorithms.
• (Dynamic Streams) Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying c-bounded arboricity graph, we present an one-pass algorithm that uses space Õ(c10/3 n2/3 )
and returns an O(c)-estimator for the size of the maximum matching. This algorithm improves
the state-of-the-art Õ(cn4/5 )-space algorithms, where the Õ(.) notation hides logarithmic in n
dependencies.
In contrast to the previous works, our results take more advantage of the streaming access to the input
and characterize the matching size based on the ordering of the edges in the stream in addition to the
degree distributions and structural properties of the sparse graphs.

∗
Department of Computer Science, University of Warwick, UK. Supported in part by European Research Council grant ERC2014-CoG 647557 and a Royal Society Wolfson Research Merit Award. g.cormode@warwick.ac.uk.
†
Department of Computer Science, University of Warwick, UK. Supported by European Research Council grant ERC-2014CoG 647557. H.Jowhari@warwick.ac.uk .
‡
Rutgers University, Piscataway, NJ, USA. mortezam@dimacs.rutgers.edu.
§
Rutgers University, Piscataway, NJ, USA. muthu@cs.rutgers.edu.

1 Introduction
Problems related to (maximum) matchings in graph have a long history in Combinatorics and Computer
Science. They arise in many contexts, from choosing which advertisements to display to online users,
to characterizing properties of chemical compounds. Stable matchings have a suite of applications, from
assigning students to universities, to arranging organ donations. These have been addressed in a variety of
different computation models, from the traditional RAM model, to more recent sublinear (property testing)
and external memory (MapReduce) models. Matching has also been studied for a number of classes of input
graph: including general graphs, bipartite graphs, weighted graphs, and those with some sparsity structure.
We focus on the streaming case, where each edge is seen once only, and we are restricted to space
sublinear in the size of the graph (ie., no. of its vertices). In this case, the objective is to find (approximately)
the size of the matching. Even here, results for general graphs are either weak or make assumptions about
the input or the stream order. In this work, we seek to improve the guarantees by restricting to graphs that
have some measure of sparsity – bounded arboricity, or bounded degree. This aligns with reality, where
most massive graphs have asymptotically fewer than O(n2 ) edges.
Recently, Kapralov, Khanna, and Sudan [19] developed a streaming algorithm which computes an estimate of matching size for general graphs within a factor of O(polylog(n)) in the random-order streaming
model using O(polylog(n)) space. In the random-order model, the input stream is assumed to be chosen
uniformly at random from the set of all possible permutations of the edges. Esfandiari et al. [10] were the
first to study streaming algorithms for estimating the size of matching in bounded arboricity graphs in the
adversarial-order streaming model, where the algorithm is required to provide a good approximation for
any ordering of edges. Graph arboricity is a measure to quantify the density of a given graph. A graph
G(V, E) has arboricity c if the set E of its edges can be partitioned into at most c forests. Since a forest on
n nodes has at most n − 1 edges, a graph with arboricity c can have at most c(n − 1) edges. Indeed, by a
result of Nash-Williams [28, 29] this holds for any subgraph of a c-bounded arboricity graph G. Formally,
the Nash-Williams Theorem [28, 29] states that c = maxU ⊆V {|E(U )|/(|U | − 1)}, where |U | and |E(U )|
are the number of nodes and edges in the subgraph with nodes U , respectively. Several important families
of graphs have constant arboricity. Examples include planar graphs (that have arboricity c = 3), bounded
genus graphs, bounded treewidth graphs, and more generally, graphs that exclude a fixed minor.1
The important observation in [10] is that the size of matching in bounded arboricity graphs can be
approximately characterized by the number of high degree vertices (vertices with degree above a fixed
threshold) and the number of so called shallow edges (edges with both low degree endpoints). This characterization allows for estimation of the matching size in sublinear space by taking samples from the vertices
and edges of the graph. The work of [10] implements the characterization in Õ(cn2/3 ) space giving a O(c)
approximation of the matching size. Subsequent works [2, 26] consider alternative characterizations and
improve upon the approximation factor however they do not result in major space improvements.

1.1 Our Contributions
We present major improvements in the space usage of streaming algorithms for sparse graphs (c-bounded
Arboricity Graphs). Our main result is a polylog space algorithm that beats the nε space bound of prior
algorithms. More precisely, we show:
Theorem 1. Let G(V, E) be a graph with arboricity bounded by c. Let S be an (adversarial order) insertiononly stream of the edges of the underlying graph G. Let M ∗ be the size of the maximum matching of G (or S
interchangeably). Then, there is a randomized 1-pass streaming algorithm that outputs a (22.5c+ 6)(1+ ε)approximation to M ∗ with probability at least 1 − δ and takes O( εc2 log( 1ε ) log cn log n) space.
1

√
It can be shown that for an H-minor-free graph, the arboricity number is O(h h) where h is the number of vertices of H. [22]

1

For the case of dynamic streams (i.e, streams of inserts and deletes of edges), we design a different algorithm using Õ(c10/3 n2/3 ) space which improves the Õ(cn4/5 )-space dynamic (insertion/deletion) streaming
algorithms of [2, 3]. The following theorem states this result (proved in Section 3.3).
Theorem 2. Let G(V, E) be a graph with the arboricity bounded by c. Let M ∗ be the size of the maximum
matching of G. Let S be a dynamic stream of edge insertions and deletions of the underlying graph G of
length at most O(cn) . Let β = µ((2µ)/(µ − 2c + 1) + 1) where µ > 2c. Then, there exists a streaming
4/3
2/3
) space in expectation and outputs a (1 + ε)β approximation of M ∗ with
algorithm that takes O( β ε(nc)
4/3
probability at least 0.86.
Our algorithms for bounded arboricity graphs are based on two novel streaming-friendly characterizations of the maximum maching size. The first characterization is a modification of the characterization in
[9] which approximates the size of the maximum matching by hµ + sµ where hµ is defined as the number
of high degree vertices (vertices with degree more than a threshold µ) and sµ is the number of shallow
edges (edges with low degree endpoints). While hµ can be easily approximated by sampling the vertices
and checking if they are high degree or not, approximating sµ in sublinear space is a challenge because in
one pass we cannot determine if a sampled edge is shallow or not. The work of [9] resolves this issue by
sampling the edges at a high rate and manages to implement their characterization in Õ(cn2/3 ) space for
adversarial insert-only streams.
To bring the space usage down to Õ(c2.5 n1/2 ) (for insert-only streams), we modify the formulation of
the above characterization. We still need to approximate hµ but instead of sµ we approximate nL the number
of non-isolated vertices in the induced subgraph GL defined over the low degree vertices. Note that sµ is the
number of edges in GL . This subtle change of definition turns out to be immensely helpful. Similar to hµ we
only need to sample the nodes and check if their degrees are below a certain threshold or not, however we
carry the additional constraint that we have to avoid counting the nodes in GL that are isolated (have only
high degree nodes as neighbors). To satisfy this additional constraint, our algorithm stores the neighbors
of the sampled vertices along with a counter for each that maintains their degree in the rest of the stream.
Although we only obtain a lower bound on the degree of the neighbors, as it turns out the lower bound
information on the degree is still useful because we can ensure the number of false positives that contribute
to our estimate is within a certain limit. As result, we can approximate hµ + nL using Õ(cn1/2 ) space
which gives a (2c + 1)(2c + 2) approximation of the maximum matching size after choosing appropriate
values for µ and other parameters. This characterization is of particular importances, as it can be adapted to
work under edge deletions as well as long as the number of deletions is bounded by O(cn). Details of the
characterization and the associated algorithms are given in Lemma 4 and Section 3.2.
To obtain a polylog(n) space algorithm (and prove the claim of Theorem 1), we give a totally new
characterization. This characterization, unlike the previous ones that only depend on the parameters of the
graph, also takes the ordering of the edges in the stream into account. Roughly speaking, we characterize
the size of a maximum matching by the number of edges in the stream that have few neighbor edges in
the rest of the stream. To understand the connection with maximum matching, consider the following
simplistic special case. Suppose the input graph G is a forest composed of k disjoint stars. Observe that the
maximum matching on this graph is just to pick one edge from each star. We relate this to a combinatorial
characterization that arises from the sequence of edges in the stream: no matter how we order the edges of
G in the stream, from each star there is exactly one edge that has no neighboring edges in the remainder of
the stream (in other words, the last edge of the star in the stream). Our characterization generalizes this idea
to graphs with arboricity bounded by c by counting the α-good edges, i.e. edges that have at most α = 6c
neighbors in the remainder of the stream. We prove this characterization gives an O(c) approximation
of the maximum matching size. More important, a nice feature of this characterization is that it can be
implemented in polylog(n) space if one allows a 1 + ε approximation. The implementation adapts an idea
2

Reference

Graph class

Stream

Approx. Factor ∗

Space Bound∗∗

[19]

General

Random Order

O(polylog(n))

O(polylog(n))

[9]

Arboricity ≤ c

Insert-Only

5c + 9

Õ(cn2/3 )

Arboricity ≤ c

Insert-Only

c+2

Õ(cn2/3 )

Arboricity ≤ c

Insert/Delete

O(c)

Arboricity ≤ c

Insert-Only

(2c + 1)(2c + 2)

Õ(cn4/5 )
√
Õ(c2.5 n)

Insert/Delete

(2c + 1)(2c + 2)

Õ(c10/3 n2/3 )

Arboricity ≤ c

Insert-Only

22.5c + 6

Õ(c log2 n)

[26]
[2, 3]
This paper
This paper
This paper

Arboricity ≤ c

Table 1: Known results for estimating the size of a maximum matching in data streams. (*) In some entries,
a (1 + ε) multiplicative factor has been suppressed for concision. (**) The Õ(.) notation hides logarithmic
in n dependencies.
from the well-known L0 sampling algorithm. It runs O(log n) parallel threads each sampling the stream at
a different rate. At the end, a thread “wins” that has sampled roughly Θ(log n) elements from the α-good
edges (samples the edges with a rate of logk n where k is the number of α-good edges). The threads that
under-sample will end up with few edges or nothing while the ones that have oversampled will keep too
many α-good edges and will be terminated as result.
Table 1 summarizes the known and new results for estimating the size of a maximum matching.

1.2 Further Related Streaming Work
In the classical offline model, where we assume we have enough space to store all vertices and edges of a
graph G = (V, E), the problem of computing the maximum matching of G has been extensively studied.
The best result in this model is the 30-years-old algorithm due to Micali and Vazirani [27] with running
√
time O(m n), where n = |V | and m = |E|. A matching of size within (1 − ε) factor of a maximum
cardinality matching can be found in O(m/ε) time [17, 27]. Very recently, Duan and Pettie [5] develop a
(1 − ε)-approximate maximum weighted matching algorithm in time O(m/ε).
The question of approximating the maximum cardinality matching has been extensively studied in the
streaming model. An O(n)-space greedy algorithm trivially obtains a maximal matching, which is a 2approximation for the maximum cardinality matching [11]. A natural question is whether one can beat
the approximation factor of the greedy algorithm with O(n polylog(n)) space. Recently, it was shown
e
≃ 1.58 in one pass requires n1+Ω(1/ log log n) space
that obtaining an approximation factor better than e−1
[12, 18], even in bipartite graphs and in the vertex-arrival model, where the vertices arrive in the stream
together with their incident edges. This setting has also been studied in the context of online algorithms,
where each arriving vertex has to be either matched or discarded irrevocably upon arrival. Seminal work due
e
approximation factor in this model.
to Karp, Vazirani and Vazirani [20] gives an online algorithm with e−1
e
Closing the gap between the upper bound of 2 and the lower bound of e−1
remains one of the most
appealing open problems in the graph streaming area (see [31]). The factor of 2 can be improved on if
one either considers the random-order model or allows for two passes [21]. By allowing even more passes,
the approximation factor can be improved to multiplicative (1 − ǫ)-approximation via finding and applying
augmenting paths with successive passes [24, 25, 6, 7, 1].
Another line of research [11, 24, 32, 8] has explored the question of approximating the maximum-weight
matching in one pass and O(n polylog(n)) space. Currently, the best known approximation factor equals
4 + ε (for any positive constant ε) [4].

3

2 Preliminaries and Notations
Let G(V, E) be an undirected unweighted graph with n = |V | vertices and m = |E| edges. For a vertex
v ∈ V , let degG (v) denote the degree of vertex v in G. A matching M of G is a set of pairwise non-adjacent
edges, i.e., no two edges share a common edge. Edges in M are called matched edges; the other edges are
called unmatched. A maximum matching of graph G(V, E) is a matching of maximum size. Throughout
the paper, when we fix a maximum matching of G(V, E), we denote it by M ∗ . A matching M of G is
maximal if it is not a proper subset of any other matching in graph G. Abusing the notation, we sometimes
use M ∗ and M for the size the maximum and maximal matching, respectively. It is well-known (see for
example [23]) that the size of a maximal matching is at least half of the size of a maximum matching, i.e.,
M ≥ M ∗ /2. Thus, we say a maximal matching is a 2-approximation of a maximum matching of G. It
is known [23] that the simple greedy algorithm, where we include the newly arrived edge if none of its
endpoint are already matched, returns a maximal matching.

3 Algorithms for Bounded Arboricity Graphs
Throughout this section, hµ denotes the number of vertices in graph G = (V, E) that have degree above µ.
Let GL = (V ′ , E ′ ) be an induced subgraph of G where V ′ = {v| degG (v) ≤ µ} and (u, v) ∈ E ′ iff u and
v are both in V ′ . Note that GL might have isolated vertices. In the following we let Mµ denote the size of
maximum matching in GL .

3.1 Characterization lemmas
Lemma 3 ([9]). For a c-bounded arboricity graph G(V, E) and µ > 2c, we have hµ ≤

2µ
∗
µ−2c+1 M .

Lemma 4. For a c-bounded arboricity graph G(V, E) and µ > 2c, we have


2µ
∗
+ 1 M∗ .
M ≤ hµ + Mµ ≤
µ − 2c + 1
Proof. The lower bound is easy to see: every edge of a maximum matching either has an endpoint with
degree more than µ or both of its endpoints are vertices with degree at most µ. The number of matched
edges of the first type are bounded by hµ whereas the number of matched edges of the second type are
bounded by Mµ .
To prove the upper bound, we use the fact Mµ ≤ M ∗ and Lemma 3.
Definition 5. Let S = (e1 , . . . , em ) be a sequence of edges. We say the edge ei = (u, v) is α-good with
respect to S if max{di (u), di (v)} ≤ α where di (x) is defined as the number of the neighbors of x that
appear after the i-th location in the stream.
Lemma 6. Let µ > 2c be a (large enough) parameter. Let Eα be the set of α-good edges in an edge stream
for a graph with arboricity at most c. We have:


c
1
−
2 µ+1



M

∗

≤ |Eα | ≤




5
α + 2 M ∗,
4

4c(µ+1)
where α = max{µ − 1, µ+1−2c
}. In particular for µ = 6c − 1, we have
M ∗ ≤ 3|E6c | ≤ (22.5c + 6)M ∗

Proof. First we prove the lower bound on |Eα |. In particular we show a relation involving the number of
edges where both endpoints have low degree, sµ = |{e = (u, v)|e ∈ E, deg(u) ≤ µ, deg(v) ≤ µ}|:
4




1
c
−
hµ + sµ ≤ |Eα |.
2 µ+1
The claim in the lemma follows from the relatively loose bound that M ∗ ≤ hµ + sµ . Let H be the set of
vertices in the graph with degree above µ and let L = V \ H. Recall that hµ = |H|. Let H0 be the vertices
in H that have no neighbor in L, and let H1 = H \ H0 . First we notice that |H1 | ≥ (1 − 2c
µ )|H|. To see
this, let E ′ be the edges with at least one endpoint in H0 . By definition, every node in H0 has degree at least
µ + 1, so we have |E ′ | ≥ µ+1
2 |H0 |. At the same time, the total number of edges in the subgraph induced by
the nodes H is at most c(|H| − 1), using the arboricity assumption. Therefore,
µ+1
|H0 |
c(|H| − 1) ≥ |E ′ | ≥
2
2c
It follows that |H0 | ≤ µ+1
(|H| − 1) which further implies that
2c
2c
|H1 | ≥ (1 −
)|H| = (1 −
)hµ .
(1)
µ+1
µ+1
P
Now let dH (v) be the degree of v in the induced subgraph H. We have v∈H1 dH (v) ≤ 2c|H|,
again using the arboricity bound and the fact that summing over degrees counts each edge at most twice.
Therefore, taking the average over nodes in H1 ,
2c
dH (v) ≤
2c
1 − µ+1

for v ∈ H1 . Consequently, at least half of the vertices in H1 have their dH bounded by 4c(µ+1)
µ+1−2c (via the
′
′
Markov inequality). Let H1 be those vertices. For each v ∈ H1 we find an α-good edge. Let e∗ = (v, u)
be the last edge in the stream where u ∈ L. Then, there cannot be too many edges that neighbor (v, u)
and come after it in the stream: the total number of edges that share an endpoint with e∗ in the rest of
4c(µ+1)
the stream is bounded by max{µ − 1, 4c(µ+1)
µ+1−2c }. Consequently, for α = max{µ − 1, µ+1−2c }, we have
c
|Eα | ≥ ( 12 − µ+1
)hµ , based on the set of |H1 |/2 edges in H1′ and using (1). For α ≥ µ, Eα also contains
the disjoint set of edges from L × L, which are all guaranteed to be α-good since both their endpoints have
c
degree bounded by µ. Therefore |Eα | ≥ sµ + ( 21 − µ+1
)hµ as claimed.
To prove the upper bound on |Eα |, we notice that the subgraph containing only the edges in Eα has
4|Eα |
[14]. It follows that |Eα | ≤
degree at most α + 1. Such a graph has a matching size of at least 5(α+1)+3
5α+8
∗
4 M . This finishes the proof of the lemma.
Last, we note that in the special case of trees (or more generally, graph streams which represent forests),
a tighter approximation bound follows (for which our algorithms specified below will also apply).
Lemma 7. For trees we have M ∗ ≤ |E1 | ≤ 2M ∗ .
Proof. Let T = (V, E) be a tree with maximum matching size M ∗ . The upper bound follows by considering
E1 : the subgraph of T formed by E1 has degree at most 2, and since we are considering trees, the set E1
can have no cycles and so consists of paths. Hence, |E1 | ≤ 2M ∗ .
For the lower bound, we use induction on the number of nodes. Suppose the claim |E1 | ≥ M ∗ is true
for all trees on n nodes. We want to show that the claim remains true for trees on n + 1 nodes. The base
case n = 2 is trivially true. Given a tree T = (V, E) with n + 1 nodes, there is always a leaf w ∈ V , that
is connected to a node u where u has at most one non-leaf neighbor. If we remove the edge (u, w) from the
tree, we get a tree T ′ with n nodes and by our induction hypothesis, |E1 (T ′ )| ≥ M ∗ (T ′ ) no matter how the
stream is ordered. Fix some ordering of the stream for T ′ . We claim after inserting the edge (u, w) in the
stream (anywhere) we will have |E1 (T )| ≥ M ∗ (T ). Why? We have two cases to consider.
(1) w has no sibling in T . In this case E1 (T ) = E1 (T ′ ) ∪ {(u, w)}. This is because u must have been a
5

leaf in T ′ and as result adding (u, w) does not cause any other edge to lose the 1-goodness property.
If follows that the size of E1 increases by 1 while M ∗ increases by at most 1.
(2) w has a sibling. In this case for sure M ∗ does not increase. Although there may be a concern that the
size of E1 could drop, below we show that adding a leaf to the stream of the edges of a tree does not
cause the size of the set E1 to drop. This is enough to show that in this case as well |E1 (T )| ≥ M ∗ (T ).
To see why adding a leaf to the stream of edges cannot reduce |E1 |, assume we insert an edge e = (u, w)
in the stream where w is a newly added leaf. If u has no 1-good edges incident on it, then E1 remains as
it was. If u has one 1-good edge on it and adding e = (u, w) causes it to be kicked out of E1 , it means
e is admitted as a new member of E1 . So the loss is accounted for. If u has two 1-good edges on it,
say e1 and e2 , we show adding e cannot cause them to be ejected from E1 . To see this, assume to the
contrary that it could, and suppose (without loss of generality) the edges come in the following order in the
stream: . . . , e2 , . . . , e1 , . . . , e, . . .. The edge e2 clearly cannot be part of E1 . But e1 must have a neighboring
edge e3 incident on u, that follow it. But that means e2 was already out before adding e to the stream. A
contradiction. Finally we note that u cannot have more than two 1-good edges on it. This finishes the
proof.

√
3.2 Õ( n) space algorithm for insert-only streams
In this section, first we present Algorithm 1 that estimates Mµ + hµ and prove the following theorem.
Theorem 8. Let G(V, E) be a graph with the arboricity bounded by c. Let S be an (adversarial order)
insertion-only stream of the edges of the underlying graph G. Let β = µ((2µ)/(µ − 2c + 1) +√1) where
µ > 2c. Then, there exists an insertion-only streaming algorithm (Algorithm 1) that takes O( β εcn log n)
space in expectation and outputs a (1 + ε)β approximation of M ∗ with probability at least 0.86, where M ∗
is a maximum matching of G.
Algorithm 1: Estimate-Mµ + hµ
Initialization: Each node is sampled to set S with probability p (determined below).
Stream Processing:
forall the edges e = (u, v) in the stream do
if u ∈ S or v ∈ S then
store e in H if u ∈ S then increment d(u) else increment l(u) if numv ∈ S then increment
d(v) else increment l(v)
Post Processing:
Let S1 = {v ∈ S|d(v) ≤ µ, ∃w ∈ Γ(v) : d(w) + l(w) ≤ µ}
Let S2 be the set of vertices {v|v ∈ S, d(v) > µ}
return s = (|S1 | + |S2 |)/p
For each w in Γ(S) (the set of neighbors of nodes in S), the algorithm maintains l(w), the number
of occurrences of w observed since (the first) v ∈ S such that w ∈ Γ({v}) was added. Note that in this
algorithm, l(w) is a lower bound on the degree of w. For the output, S1 is the subset of nodes in S whose
degree is bounded by µ and additionally there is at least one neighbor of v, w, whose observed degree (d(w)
or l(w)) is at most µ. Meanwhile, S2 is the “high degree” nodes in S.
2µ
+ 1). Algorithm 1 outputs s where (1 − ε)M ∗ ≤ s ≤
Lemma 9. Let ε ∈ (0, 1) and β = µ( µ−2c+1

(1 + ε)βM ∗ with probability at least 1 − e

−ε2 M ∗ p
4β 2

.
6

Proof. First we prove the following bounds on E(s). Mµ + hµ ≤ E(s) ≤ µ(Mµ + hµ ). Let L be the set of
vertices in G that have degree at most µ and let GL be the induced graph on L. Let H = V \ L. Note that
GL might have isolated vertices. Let N be the non-isolated vertices in GL . It is clear that if the algorithm
samples v ∈ N , v will be in S1 . Likewise, if it samples a vertex w ∈ H, w will be in S2 . Given the fact that
|H| = hµ and |N | ≥ Mµ , this proves the lower bound on E(s).
The expectation may be above Mu , as the algorithm may pick an isolated vertex in GL (a vertex that is
only connected to the high-degree vertices) and include it in S1 because one of its high-degree neighbours w
was identified as low degree, i.e., w ∈ Γ(S) and l(w) ≤ µ but w ∈ H. Let u ∈ H and let U = {a1 , . . . , aµ }
be the last µ neighbours of u according to the ordering of the edges in the stream. The algorithm can only
identify u as low degree when it picks a sample from U and no samples from Γ(u) \ U . This restricts the
number of unwanted isolated vertices to at most µhµ . Together with the fact that |N | ≤ µMµ , it establishes
the upper bound on E(s).
Now using a Chernoff bound, Pr[|s − E(s)| ≤ λE(s)] ≤ e

probability at least 1 − e
Setting λ =

ε
β

−λ2 (Mµ +hµ )p
4

−λ2 M ∗ p
4

≤ e

−λ2 M ∗ p
4

. Therefore with

,
(Mµ + hµ ) − λµ(hµ + Mµ ) ≤ s ≤ µ(1 + λ)(Mµ + hµ )
and putting this and Lemma 4 together, we derive the statement of the lemma.

Algorithm 2: Estimate-M ∗

(2)

√

Initialization: Let ε ∈ (0, 1) and t = ⌈ β ε8nc ⌉ where β is as defined in Lemma 9.
Stream Processing: Do the following tasks in parallel:
(1) Greedily keep a maximal matching of size at most r ≤ t (and terminate this task if this size bound is
exceeded).
(2) Run the Estimate-(Mµ + hµ ) procedure (Algorithm 1) with parameter p ≥

8
λ2 t

where λ = βε .

Post processing: If r < t then output 2r as the estimate for M ∗ , otherwise output the result of the
Estimate-(Mµ + hµ ) procedure.
Proof of Theorem 8: Suppose M ∗ < t. Clearly the size of the maximal matching r obtained by the first
task will be less than t. In this case, M ∗ ≤ M ′ ≤ 2M ∗ . Now suppose M ∗ ≥ t. By Lemma 4, we will have
Mµ + hµ ≥ t and hence by Lemma 9, with probability at least 1 − e−2 ≥ 0.86, the output of the algorithm
will be within the promised bounds. The expected space of the algorithm is O((t + pnc) log
n). Setting
√
√
β cn
t = β 8nc/ε to balance the space costs, the space complexity of the algorithm will be O( ε log n) as
claimed.
✷

3.3 O(n2/3 ) space algorithm for insertion/deletion streams
Algorithms 1 and 2 form the basis of our solution in the more general case where the stream contains
deletions of edges as well. In the case of Algorithm 1, the algorithm has to maintain the induced subgraph
on S and the edges of the cut (S, Γ(S)). However if we allow arbitrary number of insertions and deletions,
the size of the cut (S, Γ(S)) can grow as large as O(n) even when |S| = 1. This is because each node at
some intermediate point could become high degree and then lose its neighbours because of the subsequent
deletion of edges. Therefore here in order to limit the space usage of the algorithm, we make the assumptions
that number of deletions is bounded by O(cn). Since the processed graph has arboricity at most c this forces
the number of insertions to be O(cn) as well. Under this assumption, if we pick a random vertex, still, in
expectation the number of neighbours is bounded by O(c).
7

Another complication arises from the fact that, with edge deletions, a vertex added to Γ(S) might become isolated at some point. In this case, we discard it from Γ(S). Additionally for each vertex in S ∪ Γ(S),
the counters d(v) (or l(v) depending on if it belongs to S or Γ(S)) can be maintained as before. The space
complexity of the algorithm remains O(pnc log n) in expectation as long as the arboricity factor remains
within O(c) in the intermediate graphs. In the case of Algorithm 2, we need to keep a maximal matching
)1/3 to
of size O(t). This can be done in O(t2 ) space using a randomized algorithm [3]. Setting t at ( 8βnc
ε2
rebalance the space costs, we obtain the result of Theorem 2.

3.4 The O(log2 n) space algorithm for insert-only streams
In this section we present our polylog space algorithm by presenting an algorithm for estimating |Eα | within
(1 + ε) factor. Our algorithm is similar in spirit to the known L0 sampling strategy. It runs O(log n) parallel
threads each sampling the stream at a different rate. At the end, a thread “wins” that has sampled roughly
n
Θ(log n) elements from |Eα | (samples the edges with a rate of log
|Eα | ). The threads that under-sample will
end up with few edges or nothing while the ones that have oversampled will keep too many elements of Eα
and will be aborted as result.
First we give a simple procedure (Algorithm 3) that is the building block of the algorithm.
Algorithm 3: The α-good test
Initialization: given the edge e = (u, v) in the stream, let r(u) = 0 and r(v) = 0.
forall the subsequent edges e′ = (t, w) do
if t = u or w = u then increment r(u) if t = v or w = v then increment r(v) if
max{r(u), r(v)} > α then terminate and report NOT α-good
Now we present the main algorithm (Algorithm 4) followed by its analysis.
Algorithm 4: An algorithm for approximating |Eα |
Initialization: ∀i.Xi = ∅
⊲ Xi represents the current set of sampled α-good edges.
Stream Processing:
forall the levels i ∈ {0, 1, . . . , [⌊log1+ε m⌋} in parallel do
forall the edges e do
Feed e to the active α-good tests and update Xi
1
With probability pi = (1+ε)
i add e to Xi and start a α-good test for e.
Let |Xi | be the number of active α-good tests within this level.
2
n
if |Xi | > τ = 64αcεlog
then terminate level i
2
Post processing:
if |X0 | ≤ τ then
return |X0 |
else
⊲ |X0 | > τ
and the j-th level was not terminated;
let j be the smallest integer such that Xj ≤ 8 log n(1+ε)
ε2
Xj
if there is no such j then return FAIL else return pj
Lemma 10. With high probability, Algorithm 4 outputs a 1 ± O(ε) approximation of |Eα |.
Proof. It is clear that if |X0 | ≤ τ then X0 = Eα and the algorithm makes no error. In case |X0 | > τ , we
claim that |Eα | > 2αc 2 τ . To prove this let t be the time step where |X0 | exceeds τ and let Gt = (V, E (t) )
8

be the graph where E (t) = {e1 , . . . , et }. Clearly M ∗ (G) ≥ M ∗ (Gt ) because the size of matching only
increases. Abusing the notation, let Eα (Gt ) denote the set of α-good edges at time t. By Lemma 6, we have


5
2µ
2α2
τ < |Eα (Gt )| ≤
α + 2 M ∗ (Gt ) ≤ 4αM ∗ (G) ≤
4α|Eα | ≤
|Eα |.
4
µ − 2c
c
This proves the claim.
n
and let i∗ be the integer such
Therefore in the following we assume that |Eα | > 2αc 2 τ . Let τ ′ = 8 log
ε2
∗
∗
′
i
−1
′
i
that (1 + ε)
τ ≤ |Eα | ≤ (1 + ε) τ .
τ′
≤ E[|Xi∗ |] ≤ τ ′ . By a
Assuming the i∗ -th level does not terminate before the end, we have (1+ε)
Chernoff bound, for each i we have (again assuming we do not terminate the corresponding level)

 2
ε pi |Eα |
.
Pr[||Xi | − E(|Xi |)| ≥ εE(|Xi |)] ≤ exp −
4
2

ε |Eα |
2 log n
−1 ).
Therefore, Pr[||Xi∗ | − E(|Xi∗ |)| ≥ εE(|Xi∗ |)] ≤ exp (− 2(1+ε)
i∗ ) ≤ exp ( 1+ε ) ≤ O(n

As a result, with high probability |Xi∗ | ≤ 8 log n(1+ε)
. Moreover for all i < i∗ − 1, the corresponding
ε2
levels either terminate prematurely or in the end we will have |Xi | > 8 log n(1+ε)
with high probability.
ε2
∗
∗
∗
∗
Consequently j ∈ {i , i − 1}. It remains to prove that runs corresponding to i and i − 1 will survive until
the end with high probability. We prove this for i∗ . The case of i∗ − 1 is similar.
(t)
Consider a fixed time t in the stream and let Xi∗ be the set of sampled α-good edges at time t corre(t)
sponding to the i∗ -th level. Note that Xi∗ contains the a subset of α-good edges with respect to the stream
St = (e1 , . . . , et ). From the definition of i∗ and our earlier observations we have
2α2 |Eα |
2α2 τ ′
|Eα (Gt )|
(t)
≤
≤
E[|Xi∗ |] =
∗
∗
(1 + ε)i
c(1 + ε)i
c
By the Chernoff inequality for δ ≥ 1,


i
h
−δ
(t)
(t)
(t)
Pr |Xi∗ | ≥ (1 + δ)E(|Xi∗ |) = τ ≤ exp
E(|Xi∗ |) .
3
From δ =

τ
(t)
E(|Xi∗ |)

∗

−1 =

τ (1+ε)i
|Eα (Gt )|

− 1, we get




−τ
|Eα (Gt )|
2α2 τ ′
−τ
≥ τ ≤ exp
Pr
+
+
≤ exp
3
(1 + ε)i∗
3
c
8α2 τ ′
For τ ≥ c , the term inside the exponent is smaller than −2 log n. It also satisfies δ ≥ 1. After
h

(t)
|Xi∗ |

i



(t)

applying the union bound, for all t the size of Xi∗ is bounded by τ =
finished the proof of the lemma.

64α2 log n
cε2

with high probability. This

Next, putting everything together, we prove Theorem 1.
Proof of Theorem 1: The theorem follows from Lemmas 6 and 10 and taking α = µ + 1 = 6c. Observe
that the space cost of Algorithm 4 can be bounded: we have log1+ε m levels where each level runs at
most τ concurrent α-good tests otherwise it will be terminated. Each α-good test keeps an edge and two
counters and as result it occupies O(1) space. Consequently the space usage of the algorithm is bounded by
O(τ log1+ε m). The space bound in the theorem follows from the facts that τ = O( εc2 log n) for α = 6c
and m ≤ cn.
✷

References
[1] K. J. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467,
2012.
9

[2] M. Bury and C. Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams.
In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pages 263–274, 2015.
[3] R. Chitnis, G. Cormode, H. Esfandiari, M.T. Hajiaghayi, A. McGregor, M. Monemizadeh, and
S. Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1326–1344, 1326-1344.
[4] M. Crouch and D. S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted
matching. In Proceedings of the 17th International Workshop on Randomization and Approximation
Techniques in Computer Science (RANDOM), pages 96–104, 2014.
[5] R. Duan and S. Pettie. Linear-time approximation for maximum weight matchings. Journal of the
ACM, 61(1):1–23, 2014.
[6] S. Eggert, L. Kliemann, P. Munstermann, and A. Srivastav. Bipartite graph matchings in the semistreaming model. Algorithmica, 63(1-2):490–508, 2012.
[7] Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in
the semi-streaming model. Algorithmica, 63(1-2):490–508, 2012.
[8] Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved approximation guarantees for
weighted matching in the semi-streaming model. SIAM J. Discrete Math., 25(3):1251–1265, 2011.
[9] H. Esfandiari, M.T. Hajiaghyi, V. Liaghat, M. Monemizadeh, and K. Onak. Streaming algorithms
for estimating the matching size in planar graphs and beyond. In Proceedings of the 26th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
[10] Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and
Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1217–1233, 2015.
[11] J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming
model. Theoretical Computer Science, 348(2):207–216, 2005.
[12] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the 23rd Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 468–485, 2012.
[13] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302–
343, 2002.
[14] Yijie Han. Matching for graphs of bounded degree. In Frontiers in Algorithmics, Second Annual
International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings, pages 171–
173, 2008.
[15] Yijie Han. Matching for graphs of bounded degree. In Frontiers in Algorithmics, pages 171–173.
Springer, 2008.
[16] A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and
testing. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS),
pages 22–31, 2009.
10

[17] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs.
SIAM J. Comput., 2(4):225–231, 1973.
[18] M. Kapralov. Better bounds for matchings in the streaming model. Proceedings of the 23rd Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679–1697, 2013.
[19] M. Kapralov, S. Khanna, and M. Sudan. Approximating matching size from random streams. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 734–751,
2014.
[20] R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching.
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358,
1990.
[21] C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in semi-streaming with few passes. In
Proceedings of the 11th International Workshop on Randomization and Approximation Techniques in
Computer Science (RANDOM), pages 231–242, 2012.
[22] Alexandr V. Kostochka. Lower bound of the hadwiger number of graphs by their average degree.
Combinatorica, 4(4):307–316, 1984.
[23] L. Lovasz and M.D. Plummer. Matching theory. In North-Holland, Amsterdam-New York, 1986.
[24] A. McGregor. Finding graph matchings in data streams. In Proceedings of the 8th International
Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages
170–181, 2005.
[25] A. McGregor. Graph mining on streams. In Encyclopedia of Database Systems, pages 1271–1275.
Springer, 2009.
[26] A. McGregor and S. Vorotnikova. Planar matching in streams revisited. In Proceedings of the 19th
International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2016.
p
[27] S. Micali and V. V. Vazirani. An o( |V ||e|) algorithm for finding maximum matching in general
graphs. Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS), pages
17–27, 1980.
[28] C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London
Mathematical Society, 36(1):445–450, 1961.
[29] C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39(1):12, 1964.
[30] H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local improvements. In
Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 327–
336, 2008.
[31] List of open problems in sublinear algorithms: Problem 60. http://sublinear.info/60.
[32] Mariano Zelke. Weighted matching in the semi-streaming model. Algorithmica, 62(1-2):1–20, 2012.

11

