Maximum Matching in Two, Three, and a Few More Passes
Over Graph Streams

arXiv:1702.02559v3 [] 21 Apr 2017

Sagar Kale1 and Sumedh Tirodkar2
1 Dartmouth
2 TIFR,

College. Email: sag (at) cs.dartmouth.edu
Mumbai. Email: sumedh.tirodkar (at) tifr.res.in

Abstract
We consider the maximum matching problem in the semi-streaming model formalized by
Feigenbaum, Kannan, McGregor, Suri, and Zhang [13] that is inspired by giant graphs of today.
As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free
graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general
graphs by Konrad, Magniez, and Mathieu [20]. In three passes, we are able to achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We
also give a multi-pass algorithm where we bound the number of passes precisely—we give a
(2/3 − ε)-approximation algorithm that uses 2/(3ε) passes for triangle-free graphs and 4/(3ε)
passes for general graphs. Our algorithms are simple and combinatorial, use O(n log n) space,
and (can be implemented to) have O(1) update time per edge.
For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes:
• Ahn and Guha [1] give a (2/3 − ε)-approximation algorithm that uses O(log(1/ε)/ε2 )
passes, whereas our (2/3 − ε)-approximation algorithm uses 4/(3ε) passes;

• they also give a (1 − ε)-approximation algorithm that uses O(log n · poly(1/ε)) passes,
where n is the number of vertices of the input graph; although our algorithm is (2/3 − ε)approximation, our number of passes do not depend on n.

Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes [9] or the constant cannot be determined due to the involved analysis [22, 1], so
our multi-pass algorithm should use much fewer passes for approximation ratios bounded
slightly below 2/3.

1 Introduction
Maximum matching is a well-studied problem in a variety of computational models. We consider it in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and
Zhang [13] that is inspired by generation of ginormous graphs in recent times. A graph stream
is an (adversarial) sequence of the edges of a graph, and a semi-streaming algorithm must access
the edges in the given order and use O(n polylog n) space only, where n is the number of vertices; note that a matching can have size Ω(n), so Ω(n log n) space is necessary. The number of
times an algorithm goes over a stream of edges is called the number of passes. A trivial (1/2)approximation algorithm that can be easily implemented as a one-pass semi-streaming algorithm
is to output a maximal matching. Since the formalization of the semi-streaming model more than
a decade ago, the problem of finding a better than (1/2)-approximation algorithm or proving that
one cannot do better has baffled researchers [21]. In a step towards resolving this, Goel, Kapralov,
and Khanna [14] proved that for any ε > 0, a one-pass semi-streaming (2/3 + ε)-approximation
algorithm does not exist; Kapralov [16], building on those techniques, showed non-existence of
one-pass semi-streaming (1 − 1/e + ε)-approximation algorithms for any ε > 0. A natural next
question is: Can we do better in, say, two passes or three passes? In answering that, Konrad,
Magniez, and Mathieu [20] gave three-pass and two-pass algorithms that output matchings that
are better than (1/2)-approximate. In this work, we give algorithms that improve their approximation ratios for two-pass and three-pass algorithms. We also give a multi-pass algorithm that
does better than the best known multi-pass algorithms for at least initial few passes. We are able
to bound the number of passes precisely: we give a (2/3 − ε)-approximation algorithm that uses
2/(3ε) passes for triangle-free graphs and 4/(3ε) passes for general graphs. Earlier works either
have a large constant inside the big-O notation for the number of passes [9] or the constant cannot be determined due to the involved analysis [22, 1]. For example, the (1 − ε)-approximation
algorithm by Eggert et al. [9] potentially uses 288/ε5 passes, and for the (1 − ε)-approximation
algorithms by McGregor [22] and Ahn and Guha [1], the constants inside the big-O bound cannot
be determined due to the involved analysis. The (2/3 − ε)-approximation algorithm by Feigenbaum et al. [13] uses O(log(1/ε)/ε) passes, which is O(log(1/ε)) factor larger than the number of
passes we use to get the same approximation ratio. Our algorithms are simple and combinatorial,
use O(n log n) space, and (can be implemented to) have O(1) update time per edge. We also give
an explicit and tight analysis of the three-pass algorithm by Konrad et al. [20] that is reminiscent
of Feigenbaum et al.’s [13] multi-pass algorithm.
Technical overview: If we can find a matching M such that there are no augmenting paths of
length 3 in M ∪ M ∗ , where M ∗ is a maximum matching, then M is (2/3)-approximate, i.e., (1/2 +
1/6)-approximate. This is because, in each connected component of M ∪ M ∗ , the ratio of Medges to M ∗ -edges is at least 2/3. This is the basis for the (2/3 − ε)-approximation algorithm by
Feigenbaum et al. [13] that uses O(log(1/ε)/ε) passes. The same idea is used by Konrad et al. [20]
in the analysis of their two-pass algorithms. In the first pass, they find a maximal matching M0
and some subset of support edges, say S. If M0 is so bad that M0 ∪ M ∗ is almost entirely made up
of augmenting paths of length 3 (i.e., | M0 | ≈ | M ∗ |/2), then by the end of the second pass, they
manage to augment (using length-3 augmentations) a constant fraction of M0 using S and a fresh
access to the edges, resulting in a better than (1/2)-approximation. On the other hand, if M0 is not
so bad, then they already have a good matching. One limitation this idea faces is that a fraction of
the edges in S may become useless for an augmentation if both its endpoints get matched in M0
by the end of the first pass. Our main result is a two-pass algorithm (described in Section 5) that
differs in two ways from the former approach. Firstly, in the first pass, we only find a maximal
1

matching M0 so that in the second pass, where we maintain a set S of support edges, S would
not contain “useless” edges. Secondly, any augmentation in our algorithm happens immediately
when an edge arrives if it forms an augmenting path of length 3 with edges in M0 and S.
Our results: In light of the discussion so far, one way to evaluate an algorithm is how much
advantage it gains over the (1/2)-approximate maximal matching found in the first pass. We
summarize our two-pass and three-pass results in Table 1 and multi-pass results in Table 2. We
stress that we are able to bound the number of passes precisely, without big-O notation. For general
graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of
number of passes—see the third multi-row of Table 2. We note that our multi-pass algorithm is
not just a repetition of the second pass of our two-pass algorithm. Such a repetition will give
an asymptotically worse number of passes (see, for example, the multi-pass algorithm due to
Feigenbaum et al. [13]; the first row of Table 2). We carefully choose the parameters for each pass
to get the required number of passes. Also note that Table 1 shows advantages over a maximal
matching—an algorithm is said to have advantage α if it is a (1/2 + α)-approximation algorithm
(because a maximal matching is (1/2)-approximate).
Table 1: Advantages over a maximal matching—advantage α means (1/2 + α)-approximation.
Problem
Bipartite two-pass
Bipartite three-pass
Triangle-free two-pass
Triangle-free three-pass
General two-pass
General three-pass

Previous work
Esfandiari et al. [11]
Esfandiari et al. [11]

Advantage
1/12
1/9.52

Not considered separately
Konrad et al. [20]
1/140
Not considered separately

Advantage in this work
Not considered separately
1/16
(in Section 5)
1/10
(in Section A)
1/32
(in Section 5)
1/19.753 (in Section B)

Table 2: Multi-pass algorithms—see Section 6.
Graph
Bipartite
Triangle free
General

Results
Feigenbaum et al. [13]
Eggert et al.[9]
Ahn and Guha [1]
This work (in Section 6)
McGregor [22] randomized
Ahn and Guha [1]
Ahn and Guha [1]
This work (in Section 6)

Approx
2/3 − ε
1−ε
1−ε
2/3 − ε
1−ε
2/3 − ε
1−ε
2/3 − ε

# Passes
O(log(1/ε)/ε)
288/ε5
O(log log(1/ε)/ε2 )
2/(3ε)
O((1/ε)1/ε )
O(log(1/ε)/ε2 )
O(log n · poly(1/ε))
4/(3ε)

Note of independent work The work of Esfandiari et al. [11] who claim better approximation
ratios for bipartite graphs in two passes and three passes is independent and almost concurrent. Our
work differs in several aspects. We consider triangle-free graphs (superset of bipartite graphs) and
general graphs, and we additionally consider multi-pass algorithms. Also, their algorithm has a
2

√
post-processing step that uses time O( n · | E|), whereas our algorithms can be implemented to
have O(1) update time per edge. One further detail about this appears in Section D.

1.1 Related Work
Karp, Vazirani, and Vazirani [18] gave the celebrated (1 − 1/e)-competitive randomized online
algorithm for bipartite graphs in the vertex arrival setting. Goel et al. [14] gave the first one-pass
deterministic algorithm with the same approximation ratio, i.e., 1 − 1/e, in the semi-streaming
model in the vertex arrival setting. For the rest of this section, results involving ε hold for any ε >
0. As mentioned earlier, Goel, Kapralov, and Khanna [14] proved nonexistence of one-pass (2/3 +
ε)-approximation semi-streaming algorithms, which was extended to (1 − 1/e + ε)-approximation
algorithms by Kapralov [16]. On the algorithms side, nothing better than outputting a maximal
matching, which is (1/2)-approximate, is known. Closing this gap is considered an outstanding
open problem in the streaming community [21].
On the multi-pass front, in the semi-streaming model, Feigenbaum et al. [13] gave a (2/3 −
ε)-approximation algorithm for bipartite graphs that uses O(log(1/ε)/ε) passes; McGregor [22]
improved it to give a (1 − ε)-approximation algorithm for general graphs that uses O((1/ε)1/ε )
passes. For bipartite graphs, this was again improved by Eggert et al. [9] who gave a (1 − ε)approximation O((1/ε)5 )-pass algorithm. Ahn and Guha [1] gave a linear-programming based
(1 − ε)-approximation O(log log(1/ε)/ε2 )-pass algorithm for bipartite graphs. For general graphs,
their (1 − ε)-approximation algorithm uses number of passes proportional to log n, so it is worse
than that of McGregor [22].
For the problem of one-pass weighted matching, there is a line of work starting with Feigenbaum et al. [13] giving a 6-approximation semi-streaming algorithm. Subsequent results improved
this approximation ratio: see McGregor [22], Zelke [24], Epstein et al. [10], Crouch and Stubbs [8],
Grigorescu et al.[15], and most recently in a breakthrough, giving a (2 + ε)-approximation semistreaming algorithm, Paz and Schwartzman [23]. The multi-pass version of the problem was considered first by McGregor [22], then by Ahn and Guha [1]. Chakrabarti and Kale [5] and Chekuri
et al. [6] consider a more general version of the matching problem where a submodular function
is defined on the edges of the input graph.
The problem of estimating the size of a maximum matching (instead of outputting the actual
matching) has also been considered. We mention Kapralov et al. [17], Esfandiari et al. [12], Bury
and Schwiegelshohn [4], and Assadi et al. [2].
In the dynamic streams, edges of the input graph can be removed as well. The works of
Konrad [19], Assadi et al. [3], and Chitnis et al. [7] consider the maximum matching problem in
dynamic streams.

1.2 Organization of the Paper
After setting up notation in Section 2, we give a tight analysis of the three-pass algorithm for
bipartite graphs by Konrad et al. [20] in Section 3. In Section 4, we see our simple two-pass algorithm for triangle-free graphs. Then in Section 5, we see our main result—the improved two-pass
algorithm, and then we see the multi-pass algorithm in Section 6. The results that are not covered
in the main sections are covered in the appendix.

3

2 Preliminaries
We work on graph streams. The input is a sequence of edges (stream) of a graph G = (V, E),
where V is the set of vertices and E is the set of edges; a bipartite graph is denoted as G =
( A, B, E). A streaming algorithm may go over the stream a few times (multi-pass) and use space
O(n polylog n), where n = |V |. In this paper, we give algorithms that make two, three, or a few
more passes over the input graph stream. A matching M is a subset of edges such that each
vertex has at most one edge in M incident to it. The maximum cardinality matching problem, or
maximum matching, for short, is to find a largest matching in the given graph. Our goal is to
design streaming algorithms for maximum matching.
For a subset F of edges and a subset U of vertices, we denote by U ( F ) ⊆ U the set of vertices in
U that have an edge in F incident on them. Conversely, we denote by F (U ) ⊆ F the set of edges in
F that have an endpoint in U. For a subset F of edges and a vertex v ∈ V ( F ), we denote by NF (v)
the set of v’s neighbors in the graph (V ( F ), F ), and we define degF (v) := | NF (v)|.
In the first pass, our algorithms compute a maximal matching which we denote by M0 . We use
M ∗ to indicate a matching of maximum cardinality. Assume that M0 and M ∗ are given. For i ∈
{3, 5, 7, . . . }, a connected component of M0 ∪ M ∗ that is a path of length i is called an i-augmenting
path (nonaugmenting otherwise). We say that an edge in M0 is 3-augmentable if it belongs to a
3-augmenting path, otherwise we say that it is non-3-augmentable.
Lemma 2.1 (Lemma 1 in [20]). Let α > 0, M0 be a maximal matching in G, and M ∗ be a maximum
matching in G such that | M0 | 6 (1/2 + α)| M ∗ |. Then the number of 3-augmentable edges in M0 is at
least (1/2 − 3α)| M ∗ |, and the number of non-3-augmentable edges in M0 is at most 4α| M ∗ |.
Proof. Let the number of 3-augmentable edges in M0 be k. For each 3-augmentable edge in M0 ,
there are two edges in M ∗ incident on it. Also, each non-3-augmentable edge in M0 lies in a
connected component of M0 ∪ M ∗ in which the ratio of the number of M ∗ -edges to the number of
M0 -edges is at most 3/2. Hence,
3
| M ∗ | 6 2k + (| M0 | − k)
2 


1
3
∗
+ α |M | − k
6 2k +
2
2


1
3 3
= k+
+ α | M∗ | ,
2
4 2

since there are | M0 | − k non-3-augmentable edges ,
because | M0 | 6 (1/2 + α)| M ∗ | ,

which, after simplification, gives k > (1/2 − 3α)| M ∗ |. And the number of non-3-augmentable
edges in M0 is | M0 | − k 6 | M0 | − (1/2 − 3α)| M ∗ | 6 (1/2 + α − 1/2 + 3α)| M ∗ | = 4α| M ∗ |.
We make the following simple, yet crucial, observation.
Observation 2.1. Let M0 be a maximal matching. Then V ( M0 ) is a vertex cover, and there is no edge
between any two vertices in V \ V ( M0 ). Therefore, even if the input graph is not a bipartite graph, the
set of edges incident on V \ V ( M0 ), i.e., E(V \ V ( M0 )) give rise to a bipartite graph with bipartition
(V \ V ( M0 ), V ( M0 )).
For all the algorithms in this paper, it can be verified that their space complexity is O(n log n)
and update time per edge is O(1). We also ignore floors and ceilings for the sake of exposition.

4

B \ B ( M0 )

A ( M0 )

B ( M0 )

A \ A ( M0 )

M0
M∗
MA
MB
Figure 1: Example: state of variables in an execution of Algorithm 1.

3 Analyzing the Three Pass Algorithm for Bipartite Graphs
We analyze the three-pass algorithm for bipartite graphs given by Konrad et al. [20], i.e., Algorithm 1 by considering the distribution of lengths of augmenting paths. We also give a tight
example.
Algorithm 1 Three-pass algorithm for bipartite graphs due to Konrad et al. [20]
1: In the first pass, find a maximal matching M0 .
2: In the second pass, find a maximal matching
• M A in F2 := {ab : a ∈ A( M0 ), b ∈ B \ B( M0 )} (see Figure 1).

3:

In the third pass, find a maximal matching

• MB in F3 := {ab : a ∈ A \ A( M0 ) and ∃ a′ ∈ A( M A ) such that a′ b ∈ M0 }.

4:

Augment M0 using edges in M A and MB and return the resulting matching M.

Theorem 3.1. Algorithm 1 is a three-pass, semi-streaming, (1/2 + 1/10)-approximation algorithm for
maximum matching in bipartite graphs.
Proof. Without loss of generality, let M ∗ be a maximum matching such that all nonaugmenting
connected components of M0 ∪ M ∗ are single edges. For i = {3, 5, 7, . . . }, let ki denote the number
of i-augmenting paths in M0 ∪ M ∗ , and let k = | M0 ∩ M ∗ |. Then

| M0 | = k + ∑
i

i−1
ki
2

and

| M∗ | = k + ∑
i

i+1
ki .
2

(1)

Consider an i-augmenting path b1 a1 b2 a2 b3 · · · b(i+1)/2 a(i+1)/2 in M0 ∪ M ∗ , where for each j, we
have a j ∈ A and b j ∈ B. We call the vertex a(i−1)/2 a good vertex, because an edge in M A incident
to a(i−1)/2 can potentially be augmented using the edge b(i+1)/2 a(i+1)/2 . To elaborate, consider the
set of all edges in M A incident on good vertices; call it M ′A . Consider the set of edges of the type
b(i+1)/2 a(i+1)/2 from each i-augmenting path; call it M F . Note that M F is a matching. Then we can
augment M0 using M ′A and M F by as much as | M ′A |.
There is a matching of size ∑i ki in F2 formed by edges of the type b1 a1 from each i-augmenting
path. Since M A is maximal in F2 , we have | M A | > (∑i ki )/2. Now, the number of good vertices is
∑i ki ; therefore, the number of bad (i.e., not good) vertices is | M0 | − ∑i ki . So the number of edges

5

B \ B ( M0 )

A ( M0 )

B ( M0 )

A \ A ( M0 )

M0
M∗
MA
Figure 2: Tight example for Algorithm 1: M A has only one edge that lands on a bad vertex and
cannot be augmented in the third pass. So | M | = | M0 | = 3 and | M ∗ | = 5.
in M A incident on good vertices (see Figure 2)
∑ k
| M ′A | > i i −
2

| M0 | − ∑ k i
i

!

=

3
k i − | M0 | .
2∑
i

Let BG := {b ∈ B : ∃ a ∈ A( M ′A ) such that ab ∈ M0 }. Let M ′F ⊆ M F be defined as M ′F := {ba ∈
M F : b ∈ BG }. Then we know that | M ′F | = | M ′A | and M ′F ⊆ M F ⊆ F3 . Since we select a maximal
matching in F3 in the third pass,

| MB | >

| M ′A |
| M ′F |
3
| M0 |
=
= ∑ ki −
.
2
2
4 i
2

(2)

So the output size

| M | = | M0 | + | M B |
| M0 |
3
> | M0 | + ∑ k i −
4 i
2
=

by (1) and (2),

| M0 | 3
+ (| M ∗ | − | M0 |)
2
4

by (1), ∑ ki = | M ∗ | − | M0 | ,
i

i.e., | M | > 3| M ∗ |/4 − | M0 |/4, but we also have | M | > | M0 |, hence


3 ∗
1
| M | > max | M0 |, | M | − | M0 | .
4
4
So the bound is minimized when | M0 | = 3| M ∗ |/4 − | M0 |/4 = 3| M ∗ |/5 = (1/2 + 1/10)| M ∗ |.
As we can see in the proof above, the worst case happens when | M | = | M0 | = 3| M ∗ |/5.
Setting k3 = k5 > 1, k = 0, and ki = 0 for i > 5 gives us the tight example shown in Figure 2.

4 A Simple Two Pass Algorithm for Triangle Free Graphs
Before seeing our main result, we see a simple two pass algorithm for triangle-free graphs. The
function S EMI () in Algorithm 2 greedily computes a subset of edges such that each vertex in X has
degree at most one and each vertex in Y has degree at most λ; we call such a subset a (λ, X, Y )semi-matching (Konrad et al. [20] call this a λ-bounded semi-matching). In Algorithm 2, we find a
maximal matching M0 in the first pass, and, in the second pass, we find a (λ, V ( M0 ), V \ V ( M0 ))semi-matching S. After the second pass, we greedily augment edges in M0 one by one using edges
in S.
6

Algorithm 2 Two-pass algorithm for triangle-free graphs
1: In the first pass: M0 ← maximal matching
2: In the second pass: S ← S EMI ( λ, V ( M0 ), V \ V ( M0 )) (see Figure 3).
3: After the second pass, augment M0 greedily using edges in S to get M; output M.
4: function S EMI (λ, X, Y)
⊲ based on Algorithm 7 in Konrad et al. [20]
5:
S←∅
6:
foreach edge xy such that x ∈ X, y ∈ Y do
7:
if degS ( x) = 0 and degS (y) 6 λ − 1 then
8:
S ← S ∪ { xy}
u6

v6

u5

v5

u4

v4

u3

v3
M0

u2

v2

u1

v1

S

Figure 3: Example showing M0 and S at the end of the second pass of Algorithm 2 with λ = 2.
When we greedily augment M0 after the second pass, we may choose to augment u5 v5 and lose
two possible augmentations of edges u4 v4 and u6 v6 .
Theorem 4.1. Algorithm 2 is a two-pass, semi-streaming, (1/2 + 1/20)-approximation algorithm for
maximum matching in triangle-free graphs.
Proof. As in the proof of Theorem 3.1, let M ∗ be a maximum matching such that all nonaugmenting connected components of M0 ∪ M ∗ are single edges. For i = {3, 5, 7, . . . }, let ki denote the
number of i-augmenting paths in M0 ∪ M ∗ , and let k denote the number of edges in M ∗ ∩ M0 .
Now, we define good vertices. Consider an i-augmenting path x1 y1 x2 y2 x3 · · · x(i+1)/2 y(i+1)/2 in
M0 ∪ M ∗ . We call the vertices y1 ∈ V ( M0 ) and x(i+1)/2 ∈ V ( M0 ) good vertices, because the edges
x1 y1 ∈ M ∗ and x(i+1)/2 y(i+1)/2 ∈ M ∗ can potentially be added to S by our algorithm. Denote by
VG the set of good vertices and by VB := V ( M0 ) \ VG the set of bad vertices. Then |VG | = 2 ∑ i ki .
Note that VG ∩ VB = ∅ and VG ∪ VB = V ( M0 ) by definition.
Let VNC := VG \ V (S) be the set of good vertices not covered by S. An edge uv ∈ M ∗ with
u ∈ V \ V ( M0 ) and v ∈ VNC was not added to S, because degS (u) = λ. Hence
λ|VNC | 6 |V ( M0 )| − |VNC |

i.e.,

7

|VNC | 6

2
| M0 | ,
λ+1

(3)

because at most |V ( M0 )| − |VNC | vertices in V ( M0 ) are covered by S. Now,

|V ( M0 ) \ V (S)| = |VG \ V (S)| + |VB \ V (S)|
∵ VG ∩ VB = ∅ and VG ∪ VB = V ( M0 ),
6 |VNC | + |VB |
∵ VNC = VG \ V (S) and |VB \ V (S)| 6 |VB |,
2
6
| M0 | + |V ( M0 )| − |VG |
by (3) and the fact |VB | = |V ( M0 )| − |VG |,
λ+1
2
| M0 | + |V ( M0 )| − 2 ∑ ki because |VG | = 2 ∑ ki .
=
λ+1
i
i
Using |V ( M0 )| = |V ( M0 ) \ V (S)| + |V ( M0 ) ∩ V (S)| and the above, we get
2
|V ( M0 ) ∩ V (S)| > |V ( M0 )| −
| M0 | + |V ( M0 )| − 2 ∑ ki
λ+1
i
!
1
= 2 ∑ ki −
| M0 | .
λ+1
i

!
(4)

We observe that at most | M0 | vertices in V ( M0 ) (one endpoint of each edge) can be covered by S
without having both endpoints of an edge in M0 covered. Hence, at least |V ( M0 ) ∩ V (S)| − | M0 |
edges in M0 have both their endpoints covered by S, which, by (4), is at least
!
1
λ+3
2 ∑ ki −
| M0 | − | M0 | = 2 ∑ k i −
| M0 | .
(5)
λ+1
λ+1
i
i
After the second pass, when we greedily augment an edge from the above edges, i.e., edges whose
both endpoints are covered by S, we may potentially lose 2(λ − 1) other augmentations (see Figure 3). To see this, consider uv ∈ M0 such that u, v ∈ V (S) and au ∈ S and vb ∈ S. The graph is
triangle free, so we know that a 6= b, and we can augment M0 using the 3-augmenting path auvb;
but we may lose at most λ − 1 edges incident to a in S and at most λ − 1 edges incident to b in S.
Therefore the number of augmentations c we get after the second pass is at least 1/(2λ − 1) times
the right hand side of (5), i.e.,
c>

2
λ+3
| M0 | .
ki −
∑
2λ − 1 i
(2λ − 1)(λ + 1)

So the output size | M | = | M0 | + c, and using the above bound on c and simplifying we get:

| M| >

2
2( λ 2 − 2)
| M0 | ;
ki +
∑
2λ − 1 i
(2λ − 1)(λ + 1)

substituting ∑i ki = | M ∗ | − | M0 |, by (1), in the above,

| M| >

2( λ 2 − λ − 3)
2
| M∗ | +
| M0 | .
2λ − 1
(2λ − 1)(λ + 1)

Using λ = 3 and the fact that M0 is 2-approximate, we get
2
3
2
3
11
| M | > | M ∗ | + | M0 | > | M ∗ | + | M ∗ | = | M ∗ | =
5
10
5
20
20
8



1
1
+
2 20



| M∗ | .

5 Improved Two Pass Algorithm
We present our main result that is a two pass algorithm in this section. In the first pass, we find
a maximal matching M0 . In the second pass, we maintain a set S of support edges xy, such that
x ∈ V \ V ( M0 ), y ∈ V ( M0 ), and degS (y) 6 λM and degS ( x) 6 λU , where λM > 1 and λU > 1 are
parameters denoting maximum degree allowed in S for matched and unmatched vertices (with
respect to M0 ), respectively. Whenever a new edge forms a 3-augmenting path with an edge in
M0 and an edge in S, we augment. Algorithm 3 gives a formal description.
Algorithm 3 Improved two-pass algorithm: input graph G
1: In the first pass, find a maximal matching M0 .
2: if G is triangle-free then
3:
Return I MPROVE -M ATCHING( M0 , 2, 1)
4: else
5:
Return I MPROVE -M ATCHING( M0 , 4, 2)
6: function I MPROVE -M ATCHING(M0 , λU , λM )
7:
M ← M0 , S ← ∅, I ← ∅ and IB ← ∅
8:
foreach edge xy in the stream do
9:
if x or y ∈ I ∪ IB then
10:
Continue, i.e., ignore xy.
11:
else if x ∈ V ( M0 ) and y ∈ V ( M0 ) then
12:
Continue, i.e., ignore xy.
13:
else if there exist v and b such that yv ∈ M0 and vb ∈ S then
14:
M ← M \ {yv} ∪ { xy, vb}
⊲ a 3-augmentation
Let Ix ← {u x , vx : xu x ∈ S and u x vx ∈ M0 }.
Let Ib ← {ub , vb : ub vb ∈ M0 and vb b ∈ S}.
15:
Then I ← I ∪ { x, y, v, b} and IB ← IB ∪ Ix ∪ Ib .
16:
else
Without loss of generality, assume that x ∈ V \ V ( M0 ) and y ∈ V ( M0 ).
17:
if degS ( x) < λU and degS (y) < λM then
⊲ See Figure 4.
18:
S ← S ∪ { xy} ⊲ Note: Once an edge is added to S, it is never removed from it.
19:

Return M.

Setting up a charging scheme to lower bound the number of augmentations
We first lay the groundwork and give a charging scheme.
Observation 5.1. For general graphs (that are possibly not triangle-free), we need to set λM > 2.
To see why, suppose λM = 1. Let uv be a 3-augmentable edge in M0 . Then, for the edge uv,
we might end up storing the edges ub and vb in S, and the edge uv would not get augmented. If
λM > 2, and we store at least λM edges incident to u, then an edge incident to v will not form a
triangle with at least one of those and uv would get augmented. So, for general graphs, we need
to set λM > 2.
Let | M0 | = (1/2 + α)| M ∗ |. For a 3-augmentable edge uv ∈ M0 , let auvb be the 3-augmenting
path such that au, vb ∈ M ∗ . Without loss of generality, assume that au arrived before vb. Then we
make the following observation.
9

a6

a4

u6

v6

u5

v5

u4

v4

u3

v3

u2

v2

u1

v1

b6

b4

M0
some M ∗ edges
some S edges

Figure 4: Example showing M0 and some of the edges in M ∗ and S during the second pass of
Algorithm 3 for triangle-free graphs with λU = 2 and λM = 1. At most one of ui and vi can have
positive degree in S, because we would rather augment ui vi instead of adding the latter edge to
S. By our convention, a4 u4 arrived before v4 b4 , and a6 u6 arrived before v6 b6 . Since a4 u4 was not
added to S, we have degS ( a4 ) = λU (S edges incident to a4 are not shown).
Observation 5.2. When au arrived, it may not be added to S for one of the following reasons:
• The vertex a was already matched.
• There were λM edges incident to u in S.
• There were λU edges incident to a in S.
We call some edges in M0 good, some partially good, and some bad. An edge is good if it got
augmented. An edge uv ∈ M0 is bad if it is 3-augmentable, not good, and vertex a or b had λU
edges incident to them in S when edge au or vb arrived. An edge uv ∈ M0 is partially good if
it is 3-augmentable, but neither good nor bad (“partially” good because, as we will see later, we
can hold some good edge u′ v′ ∈ M0 responsible for uv not getting augmented). Note that all
3-augmentable edges get some label according to our labeling. We require the following Lemma
to describe the charging scheme.
Lemma 5.1. Suppose au was not added to S because there were already λM edges incident to u in S. If,
later, uv did not get augmented when vb arrived, then
• b was already matched via augmenting path a′′ u′′ v′′ b, or
• there exists a′ u ∈ S and u′ v′ ∈ M0 such that a′ was matched via augmenting path a′ u′ v′ b′ .
Proof. When au arrived, | NS (u)| > λM . If b was unmatched when vb arrived, then some a′ ∈
NS (u) \ {b} must have been matched, otherwise we would have augmented uv. Now for trianglefree graphs b ∈
/ NS (u), so | NS (u) \ {b}| = | NS (u)| > 1, and for general graphs, by Observation 5.1,
λM > 2, so | NS (u) \ {b}| > λM − 1 > 1.

10

a

u

v

b

v′

y

partially good

a′′

u′

M0
some M ∗ edges

good

u′′

bad

some S edges
v′′

b′′

a stream edge

Figure 5: Example showing a good edge, a bad edge, and a partially good edge. We use parameters
λU = 2 and λM = 1, so we are in the triangle-free case. The edge u′ v′ is not 3-augmentable but
was augmented using a′′ u′ v′ y, so u′ v′ is a good edge. The edge u′′ v′′ is a 3-augmentable edge that
was not augmented and when a′′ u′′ arrived, degS ( a′′ ) = 2, so u′′ v′′ is a bad edge. For uv, we did
not take au in S, because degS (u) = 1, so uv is a partially good edge, and we can charge uv to u′ v′
using Lemma 5.1.
Charging Scheme. As alluded to earlier, we charge a partially good edge to some good edge.
Recall that for a 3-augmentable edge uv ∈ M0 , we denote by au, vb ∈ M ∗ the edges that form the
3-augmenting path with uv such that au arrived before vb. We use Observation 5.2 and consider
the following cases. See Figure 5.
• Suppose au was not added to S because a was already matched. Then, let u′ v′ ∈ M0 was
augmented using au′ v′ b′ . If degS ( a) 6 λU − 1, then we charge uv to u′ v′ . Otherwise, uv is
bad.
• Suppose au was not added to S because degS (u) = λM . Then we use Lemma 5.1. We either
charge uv to u′ v′ , or if degS (b) 6 λU − 1, then we charge uv to u′′ v′′ . Otherwise, uv is bad.
• Suppose au was not added to S because degS ( a) = λU , then uv is bad.
• Otherwise, au was added to S, but uv did not get augmented when vb arrived. Then:
– Either there exists a′ ∈ NS (u) that was matched via augmenting path a′ u′ v′ b′ (note that
a′ may be same as a), then we charge uv to u′ v′ ;
– or b was already matched via augmenting path a′′ u′′ v′′ b, and vb was ignored; in this
case, if degS (b) 6 λU − 1, then we charge uv to u′′ v′′ , otherwise, uv is bad.
We now bound the number of bad edges in M0 from above.
Lemma 5.2. The number of bad edges is at most λM | M0 |/λU .
Proof. We claim that for any uv ∈ M0 , degS (u) + degS (v) 6 λM , hence |S| 6 λM | M0 |. A short
argument is that the (λM + 1)th edge would cause an augmentation and will not be added to S.
Let us assume the claim. By the definition of a bad edge, λU edges in S are “responsible” for one
bad edge in M0 . Also, an edge au′ (or v′′ b, resp.) in S can be responsible for at most one bad edge
that can only be uv if au ∈
/ S (or if vb ∈
/ S, resp.; considering the 3-augmenting path auvb). Hence,
the total number of bad edges is at most |S|/λU 6 λM | M0 |/λU . Now we prove the claim.
We first prove the claim for triangle-free graphs by contradiction. Let degS (u) + degS (v) > λM ,
and let vy ∈ S be the (λM + 1)th edge incident to one of u and v that was added to S. Since λM > 1
and degS (v) 6 λM , we have degS (u) > 1, i.e. NS (u) 6= ∅. Now when vy arrived:
11

• the vertex y was unmatched, otherwise vy would not be added to S;
• no vertex x ∈ NS (u) was matched, otherwise u, v ∈ IB , and vy would not be added to S.
The above implies that when vy arrived, due to some x ∈ NS (u) the if condition on Line 14 became
true, and we augmented uv via xuvy instead of adding vy to S. This is a contradiction.
For general graphs, we argue by contradiction slightly informally for the sake of brevity. By
Observation 5.1, for general graphs, λM > 2. Let degS (u) + degS (v) > λM > 2. Let vy be the
second edge incident to one of u and v that was added to S; the first edge can be xu or vy′ .
Suppose xu was the first edge. If x 6= y, then we would have augmented uv via xuvy instead of
adding vy to S—a contradiction. If x = y, then after vy was processed, NS (u) = NS (v) = {y}, and
a third edge incident to one of u and v would not be added to S, because it would have formed a
3-augmenting path with either yu or vy, resulting in a contradiction that degS (u) + degS (v) = 2.
Otherwise, suppose vy′ was the first edge; then NS (v) = {y, y′ } after vy was processed. Since
eventually degS (u) + degS (v) > λM + 1 > 3 and degS (u), degS (v) 6 λM , we would eventually
have degS (u) > 1, so let xu ∈ S. When xu arrived, it would have formed an 3-augmenting path
with either vy or vy′ (here, taking care of the fact that one of y and y′ can be same as x), resulting
in a contradiction that xu was not added to S.
Thus, we get the claim and complete the proof.
As a consequence, we get the following.
Observation 5.3. In any call to I MPROVE -M ATCHING(), we need to set λU > λM , i.e., λU > 2.
To see why, suppose λU 6 λM . Then by Lemma 5.2, potentially all 3-augmentable edges in M0
could become bad edges.
Recall that a 3-augmentable edge is good, partially good, or bad; so by Lemmas 2.1 and 5.2,


1
λ | M0 |
− 3α | M ∗ | − M
# good or partially good edges >
2
λU




λM 1
1
∗
− 3α | M | −
+ α | M∗ |
=
2
λU 2


 
λU − λM
3λU + λM
=
−
α | M∗ | .
(6)
2λU
λU
In the following Lemma, we bound the number of partially good edges in M0 that are charged to
one good edge.
Lemma 5.3. At most 2λU − 1 partially good edges in M0 are charged to one good edge in M0 .
Proof. Suppose uv ∈ M0 was augmented by edges xu and vy such that xu arrived before vy,
then xu ∈ S. Now | NS ( x)|, | NS (y)| 6 λU . Since xu ∈ S, we have | NS ( x) \ {u}| 6 λU − 1.
Let B := ( NS ( x) \ {u}) ∪ NS (y), then | B| 6 2λU − 1. Now, the set of partially good edges that are
charged to uv is a subset of M0 ( B). Observing that | M0 ( B)| 6 | B| 6 2λU − 1 finishes the proof.
The following lemma characterizes the improvement given by I MPROVE -M ATCHING().
Lemma 5.4. Let | M0 | = (1/2 + α)| M ∗ | and M = I MPROVE -M ATCHING ( M0 , λU , λM ), then

 



1 λU − λM
3λU + λM
1 λU − λM
∗
+
+
+ 1−
α |M | >
| M∗ | .
| M| >
2
2
4λ2U
2λ2U
4λ2U
12

Proof. By (6) and Lemma 5.3, the total number of augmentations during one call to I MPROVE M ATCHING() is at least

 


 

3λU + λM
3λU + λM
1
λU − λM
λU − λM
∗
−
α | M∗ | .
−
α |M | =
2λU
2λU
λU
4λ2U
2λ2U
Hence, we get the following bound on the size of the output matching M:


λU − λM 3λU + λM
| M | > | M0 | +
−
α | M∗ |
4λ2U
2λ2U

 

3λU + λM
1 λU − λM
+
+ 1−
α | M∗ |
because | M0 | = (1/2 + α)| M ∗ | ,
=
2
4λ2U
2λ2U


1 λU − λM
>
| M∗ |
since λU > 2 (see Observation 5.3) .
+
2
4λ2U
Now we state and prove our main result.
Theorem 5.5. Algorithm 3 uses two passes and has an approximation ratio of 1/2 + 1/16 for triangle-free
graphs and an approximation ratio of 1/2 + 1/32 for general graphs for maximum matching.
Proof. By Lemma 5.4, after the second pass, the output size | M | > (1/2 + (λU − λM )/(4λ2U ))| M ∗ |;
we use λU = 2 and λM = 1 for triangle-free graphs and λU = 4 and λM = 2 (see Observation 5.1)
for general graphs to get the claimed approximation ratios.

6 Multi Pass Algorithm
We run the function I MPROVE -M ATCHING() in Algorithm 3 with increasing values of λU , and the
approximation ratio converges to 1/2 + 1/6. We note that this multi-pass algorithm is not just a
repetition of the function I MPROVE -M ATCHING(). Such a repetition will give an asymptotically
worse number of passes (see, for example, the multi-pass algorithm due to Feigenbaum et al. [13]).
We carefully choose the parameter λU for each pass to get the required number of passes.
Algorithm 4 Multi-pass algorithm: input graph G
1: In the first pass, find a maximal matching M1 .
2: M ← M1
3: if G is triangle-free then
4:
for i = 2 to ⌈2/(3ε)⌉ do
5:
M ← Improve-Matching( M, i, 1)
6:

7:
8:
9:

else
for i = 2 to ⌈4/(3ε)⌉ do
M ← Improve-Matching( M, i + 1, 2)
Return M.

Theorem 6.1. For any ε > 0, Algorithm 4 is a semi-streaming (1/2 + 1/6 − ε)-approximation algorithm
for maximum matching that uses 2/(3ε) passes for triangle-free graphs and 4/(3ε) passes for general
graphs.

13

Proof. We prove the theorem for triangle-free case; the general case is similar. Let Mi be the matching computed by Algorithm 4 after ith pass, and let p := ⌈2/(3ε)⌉, so ε 6 2/(3p). Since M1 is
maximal, it is (1/2)-approximate. Let α1 := 0, and for i ∈ {2, 3, . . . , p}, let


3i + 1
i−1
+ 1−
α i−1
αi :=
4i2
2i2
(see Lemma 5.4 with λU = i and λM = 1). Then, by Lemma 5.4 and the logic of Algorithm 4, for
i ∈ [ p], the matching Mi is (1/2 + αi )-approximate (by a trivial induction). Now we bound α p by
induction. We claim that for i ∈ [ p],
1
2
αi > − ,
6 3i
which we prove by induction on i.
Base case: For i = 1, we have 1/6 − α1 = 1/6 − 0 = 1/6 6 2/(3 · 1).
For inductive step, we want to show that


1 i−1
3i + 1
1
2
− αi = − 2 − 1 −
α i−1 6 ,
2
6
6
4i
2i
3i
which is implied by the following (using inductive hypothesis)



2
1
3i + 1
1 i−1
− 2 + 1−
−
6
6
4i
2i2
3( i − 1) 6
 2


2i − 3i − 1
4−i+1
1 i−1
− 2 +
6
6
4i
2i2
6( i − 1)

which is implied by

2
,
3i
2
,
3i

multiplying both sides by 12i2 (i − 1), we then need to show that,
which is implied by
which is implied by

2i2 (i − 1) − 3(i − 1)2 + (2i2 − 3i − 1)(−i + 5) 6 8i (i − 1)

2i3 − 2i2 − 3(i2 − 2i + 1) + (−2i3 + 10i2 + 3i2 − 15i + i − 5) 6 8i2 − 8i

which is implied by

2i3 − 5i2 + 6i − 3 + (−2i3 + 13i2 − 14i − 5) 6 8i2 − 8i
8i2 − 8i − 8 6 8i2 − 8i

which is true, so we get the claim. Therefore α p > 1/6 − 2/(3p) > 1/6 − ε, and by our earlier observation, M p is (1/2 + α p )-approximate, and this finishes the proof for triangle-free case.
The proof for general case is very similar. We define p := ⌈4/(3ε)⌉ and α1 := 0, and for i ∈
{2, 3, . . . , p}, we define


i−1
3( i + 1) + 2
αi :=
+ 1−
α i−1 ,
4( i + 1) 2
2( i + 1) 2
i.e., we use λU = i + 1 and λM = 2. The corresponding claim then is that for i ∈ [ p],
αi >

4
1
− ,
6 3i

which can be verified by induction on i.
Acknowledgements. We thank Sundar Vishwanathan and Ashish Chiplunkar for helpful
discussions. The first author would like to thank his advisor Amit Chakrabarti and Andrew McGregor for helpful discussions.
14

References
[1] Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with
application to the maximum matching problem. Inf. Comput., 222:59–79, January 2013.
[2] Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in
graph streams. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages
1723–1742, 2017.
[3] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in
dynamic graph streams and the simultaneous communication model. In Proc. 27th Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 1345–1364, 2016.
[4] Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Proc. 23rd Annual European Symposium on Algorithms, pages 263–274,
2015.
[5] Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings,
matroids, and more. Mathematical Programming, 154(1):225–247, 2015.
[6] Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Proc. 42nd International Colloquium on Automata, Languages and
Programming, pages 318–330, 2015.
[7] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling
with applications to finding matchings and related problems in dynamic graph streams. In
Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1326–1344, 2016.
[8] Michael Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Proc. 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, volume 28, pages 96–104, 2014.
[9] Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav.
matching in the semi-streaming model. Algorithmica, 63(1):490–508, 2012.

Bipartite

[10] Leah Epstein, Asaf Levin, Julian Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3):1251–1265, 2011.
[11] H. Esfandiari, M. Hajiaghayi, and M. Monemizadeh. Finding large matchings in semistreaming. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW),
pages 608–614, Dec 2016.
[12] Hossein Esfandiari, Mohammad T. Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and
Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and
beyond. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1217–1233,
2015.
[13] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On
graph problems in a semi-streaming model. Theor. Comput. Sci., 348(2):207–216, December
2005.
15

[14] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming
complexity of maximum bipartite matching. In Proc. 23rd Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 468–485, 2012.
[15] Elena Grigorescu, Morteza Monemizadeh, and Samson Zhou. Streaming weighted matchings: Optimal meets greedy. CoRR, abs/1608.01487, 2016.
[16] Michael Kapralov. Better bounds for matchings in the streaming model. In Proc. 24th Annual
ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2013.
[17] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from
random streams. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages
734–751, 2014.
[18] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line
bipartite matching. In Proc. 22nd Annual ACM Symposium on the Theory of Computing, pages
352–358, 1990.
[19] Christian Konrad. Maximum matching in turnstile streams. In Proc. 23rd Annual European
Symposium on Algorithms, pages 840–852, 2015.
[20] Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semistreaming with few passes. CoRR, abs/1112.0184, 2014.
[21] Andrew McGregor.
Problem 60:
Single-pass unweighted matchings.
http://sublinear.info/index.php?title=Open_Problems:60. Accessed: 2017-02-16.
[22] Andrew McGregor. Finding graph matchings in data streams. In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 170–181, 2005.
[23] Ami Paz and Gregory Schwartzman. A (2 + ε)-approximation for maximum weight matching in the semi-streaming model. In Proc. 28th Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 2153–2161, 2017.
[24] Mariano Zelke. Weighted matching in the semi-streaming model. In Proc. 25th International
Symposium on Theoretical Aspects of Computer Science, pages 669–680, 2008.

A

Three Pass Algorithm for Triangle Free Graphs

For completeness, we present our three-pass algorithm for triangle-free graphs.
Theorem A.1. Algorithm 5 is a three-pass, semi-streaming, (1/2 + 1/10)-approximation algorithm for
maximum matching in triangle-free graphs, and the analysis is tight.
Proof. Let | M0 | = (1/2 + α)| M ∗ |. The number of edges in M ∗ incident on V ( M ∗ ) \ V ( M0 ) is

|V ( M ∗ ) \ V ( M0 )| > |V ( M ∗ )| − |V ( M0 )| = 2| M ∗ | − 2| M0 | = (1 − 2α)| M ∗ | ;

(7)

and these edges also belong to F1 . Since M1 is a maximal matching in F1 ,

| M1 | > (1 − 2α)| M ∗ |/2 = (1/2 − α)| M ∗ | .

16

(8)

Algorithm 5 Three-pass algorithm for triangle-free graphs
1: In the first pass, find a maximal matching M0 .
2: In the second pass, find a maximal matching M1 in F1 : = {uv : u ∈ V \ V ( M0 ), v ∈ V ( M0 )}.
3: After the second pass:
• M1′ ← arbitrary largest subset of M1 such that there is no 3-augmenting path in M1′ ∪ M0
with respect to M0
• V2 ← { x ∈ V ( M0 ) : ∃v, w such that vw ∈ M1′ and wx ∈ M0 }

• For x ∈ V2 , denote by P( x) the vertex v such that there exists w with vw ∈ M1′ and
wx ∈ M0 . See x and P( x) in Figure 6.

4:
5:
6:
7:
8:
9:
10:

In the third pass: F2 := { xy : x ∈ V2 , y ∈ V \ V ( M0 )}
M2 ← ∅
for edge xy ∈ F2 do
if x, and y are unmarked then
M2 ← M2 ∪ { xy}; since the graph is triangle free, y 6= P( x), and we can augment M0
using xy.
Mark P( x), x, y, and P−1 (y) (if exists).
Let M be largest of M3 and M3′ which are computed below.
• Augment M0 using edges in M1 to get M3 .

• Augment M0 using edges in M1′ and M2 to get M3′ .

11:

Output M.

Let c be the number of 3-augmenting paths in M1 ∪ M0 , so | M1′ | = | M1 | − c by the definition
of M1′ . By Lemma 2.1, there are at most 4α| M ∗ | non-3-augmentable edges in M0 . So at least
| M1 | − c − 4α| M ∗ | edges of M1′ are incident on 3-augmentable edges of M0 . Therefore there is a
matching of size at least | M1 | − c − 4α| M ∗ | in F2 ; consider one such matching M F . We claim that
| M2 | > | M F |/4. See Figure 6. Let xy ∈ M2 ; we note that xy disallows at most four edges in M F
from being added to M2 due to the (at most) four marks that it adds, because a marked vertex can
disallow at most one edge in M F (due to it being a matching), which shows the claim. Hence:
P( x)
y

x
M0

P −1 ( y)

MF
M1′
a stream edge
Figure 6: An edge xy ∈ M2 disallows at most four edges in M F from being added to M2 .

17

B \ B ( M0 )

A ( M0 )

B ( M0 )

A \ A ( M0 )

M0
M∗
M1
Figure 7: Tight example for Algorithm 5: M1 has only two edges that land on bad vertices and
cannot be augmented in the third pass. So | M | = | M0 | = 3 and | M ∗ | = 5.

| MF |
4
| M1 | − c − 4α| M ∗ |
>

 4 
1
1
∗
∗
>
− α | M | − c − 4α| M |
4
2



1
1
∗
− 5α | M | − c .
=
4
2

| M2 | >

by (8) ,

Now, each edge in M2 gives one augmentation after the second pass. To see this, we observe
that for any x ∈ V2 , at any point in the algorithm, x and P( x) are either both marked or both
unmarked. So when an edge xy ∈ M2 arrives, x and y are unmarked, and P( x) and P−1 (y) (if it
exists) are also unmarked, otherwise one of x and y would have been marked and xy would not
have been added to M2 . Since both P( x) and P−1 (y) were unmarked, we can use the augmenting
path { M1′ ({ P( x)}), M0 ({ x}), xy}. Hence we get at least




1
1
∗
− 5α | M | − c
max c,
4
2
augmentations after the third pass. This is minimized by setting



1
1
∗
c=
− 5α | M | − c
4
2



1
1
∗
=
− 5α | M |
5
2


1
=
− α | M∗ | .
10
So we get the following bound:








1
1
1
1
1
∗
∗
∗
| M | > | M0 | +
− α |M | >
+ α |M | +
− α |M | =
+
| M∗ | .
10
2
10
2 10
The tight example is shown in Figure 7.

18

B Three Pass Algorithm for General Graphs
We find a maximal matching M1 in the first pass. Then we use I MPROVE -M ATCHING() function
from Algorithm 3, i.e.,
• in the second pass, M2 ← I MPROVE - MATCHING ( M1 , 4, 2), and
• in the third pass, M3 ← I MPROVE - MATCHING ( M2 , 5, 2).
We observe that M1 is (1/2)-approximate. Then by double application of Lemma 5.4, we get that
M3 is (1/2 + 81/1600) ≈ (1/2 + 1/19.753)-approximate.

C

Three Pass Algorithm for Bipartite Graphs: Suboptimal Analysis

We now give an analysis of Algorithm 1 that shows approximation ratio of only 1/2 + 1/18 that
is based on Konrad et al.’s [20] analysis for their two-pass algorithm for bipartite graphs. Afterward, we demonstrate that by not considering the distribution of lengths of augmenting paths, we
may prove an approximation ratio of at most 1/2 + 1/14. The better and tight analysis appears
in Section 3.
Theorem C.1. Algorithm 1 is a three-pass, semi-streaming, (1/2 + 1/18)-approximation algorithm for
maximum matching in bipartite graphs.
Proof. As usual, let | M0 | = (1/2 + α)| M ∗ |. Since M0 is a maximal matching, there are | B( M ∗ ) \
B( M0 )| edges of M ∗ that are also in F2 . We have

| B( M ∗ ) \ B( M0 )| > | B( M ∗ )| − | B( M0 )| = | M ∗ | − | M0 | ,
and since M A is maximal, we then get the following:





1
1
1 1
1
1
∗
∗
∗
+α
|M | =
− α | M ∗ |. (9)
1−
| M A | > | B( M ) \ B( M0 )| > (| M | − | M0 |) =
2
2
2
2
2 2
By Lemma 2.1, there are at most 4α| M ∗ | non-3-augmentable edges in M0 . Which means that at
least | M A | − 4α| M ∗ | edges of M A are incident on 3-augmentable edges of M0 ; therefore there is a
matching of size at least | M A | − 4α| M ∗ | in F3 . Since we output a maximal matching in F3 , we get
at least (1/2)(| M A | − 4α| M ∗ |) augmentations after the third pass. So we get the following bound:
1
| M | > | M0 | + (| M A | − 4α| M ∗ |)
2 


1 1 1
− α − 4α | M ∗ |
> | M0 | +
2 2 2


1 9
− α | M∗ |
= | M0 | +
8 4




1
1 9
∗
=
+ α |M | +
− α | M∗ |
2
8 4


1 1 5
=
+ − α | M∗ | .
2 8 4

by (9) ,

because | M0 | = (1/2 + α)| M ∗ | ,

We also have | M | > | M0 | = (1/2 + α)| M ∗ |. As α increases, the former bound deteriorates and
the latter improves, so the worst case α is when these two bounds are equal, which happens at
α = 1/18, and the approximation ratio we get is 1/2 + 1/18.
19

C.1 Improved Analysis Without Considering Longer Augmenting Paths
We can analyze Algorithm 1 better if we bound | M A | more carefully. The claim is that at least
(1/2 − 7α)| M ∗ |/2 edges of M A are incident on 3-augmentable edges of M0 . Let A G ⊆ A( M0 ) be
the set of vertices in A that are endpoints of 3-augmentable edges of M0 ; also, let A N = A( M0 ) \
A G . So there is a matching of size at least | A G | in F2 that covers A G . Any maximal matching
in F2 has at least (| A G | − | A N |)/2 edges that are incident on A G . To see the claim, we use the
facts | A G | > (1/2 − 3α)| M ∗ | and | A N | 6 4α| M ∗ |. So there is a matching of size at least (1/2 −
7α)| M ∗ |/2 in F3 . We output a maximal matching in F3 ; hence we get at least (1/2 − 7α)| M ∗ |/4
augmentations after the third pass. So we get the following bound:


1 1
| M | > | M0 | +
− 7α | M ∗ |
4 2




1 1
1
∗
+ α |M | +
− 7α | M ∗ |
=
2
4 2


1 1 3
=
+ − α | M∗ | .
2 8 4
where the second inequality is by (9). We also have | M | > | M0 | = (1/2 + α)| M ∗ |, so the worst
case α is when these two bounds are equal, which happens at α = 1/14 and the approximation
ratio we get is 1/2 + 1/14, and we get the following theorem.
Theorem C.2. Algorithm 1 is a three-pass, semi-streaming, (1/2 + 1/14)-approximation algorithm for
maximum matching in bipartite graphs.

D A Note on the Analysis by Esfandiari et al. [11]
We demonstrate with an example that the analysis of the algorithm by Esfandiari et al. [11] given
for bipartite graphs cannot be extended for triangle-free graphs to get the same approximation
ratio. See Figure 8. Lemma 6 in their paper, as they correctly claim, holds only for bipartite graphs
and not for triangle-free graphs. Our algorithm in Section 4 is essentially the same algorithm
except for the post-processing step; we augment the maximal matching computed in the first pass
greedily, whereas they use an offline maximum matching algorithm. We have highlighted some
other comparison points in Section 1.

20

a7

u7

v7

a6

u6

v6

u5

v5

b7

u4

v4

b2

u3

v3

a1

M
a2

u2

some M ∗ edges

v2

golden edges
u1

v1

Figure 8: Example demonstrating that Lemma 6 in Esfandiari et al. [11] does not hold when the
input graph is not bipartite but is triangle-free. We use k = 3. For an M edge ui vi , there are two
M ∗ edges incident on it, which are ai ui and vi bi , and some of the M ∗ edges are not shown, but
all golden edges are shown, which we call support edges or denote by S in our terminology. It
can be seen from this example that their algorithm is not a (1/2 + 1/12)-approximation algorithm
for triangle free graphs, because out of the seven 3-augmentable edges in M, only one will get
augmented, thereby giving a worse approximation ratio.

21

