# Optimal Streaming Algorithms for Graph Matching

Jianer Chen Department of Computer Science and Engineering, Texas A&M
University, College Station, TX 77843, USA. Email<EMAIL_ADDRESS>Qin
Huang Department of Computer Science and Engineering, Texas A&M University,
College Station, TX 77843, USA. Email<EMAIL_ADDRESS>Iyad Kanj School of
Computing, DePaul University, Chicago, IL 60604, USA. Email:
<EMAIL_ADDRESS>Ge Xia Department of Computer Science, Lafayette College,
Easton, PA 18042, USA. Email<EMAIL_ADDRESS>
###### Abstract

We present parameterized streaming algorithms for the graph matching problem
in both the dynamic and the insert-only models. For the dynamic streaming
model, we present a one-pass algorithm that, _w.h.p._ (with high probability),
computes a maximum-weight $k$-matching of a weighted graph in
$\tilde{O}(Wk^{2})$ space111The notation $\tilde{O}()$ hides a poly-
logarithmic factor in the input size. and that has $\tilde{O}(1)$ update time,
where $W$ is the number of distinct edge weights. For the insert-only
streaming model, we present a one-pass algorithm that runs in
$\mathcal{O}(k^{2})$ space and has $\mathcal{O}(1)$ update time, and that,
_w.h.p._ , computes a maximum-weight $k$-matching of a weighted graph. The
space complexity and the update-time complexity achieved by our algorithms for
unweighted $k$-matching in the dynamic model and for weighted $k$-matching in
the insert-only model are optimal.

A notable contribution of this paper is that the presented algorithms do not
rely on the apriori knowledge/promise that the cardinality of _every_ maximum-
weight matching of the input graph is upper bounded by the parameter $k$. This
promise has been a critical condition in previous works, and lifting it
required the development of new tools and techniques.

##  1 Introduction

Emerging applications in big-data involve processing graphs of tremendous size
[33]. For such applications, it is infeasible to store the graph when
processing it. This issue has given rise to a new computational model,
referred to as the _graph streaming model_. A graph _stream_ $\mathcal{S}$ for
an underlying graph $G$ is a sequence of elements of the form $(e,op)$, where
$op$ is an operation performed to edge $e$. In the _insert-only_ streaming
model, each operation is an edge-insertion, while in the _dynamic_ streaming
model each operation is either an edge-insertion or an edge-deletion (with a
specified weight if $G$ is weighted). The graph streaming model demands
performing the computation within limited space and time resources.

The graph matching problem, both in unweighted and weighted graphs, is one of
the most extensively-studied problems in the streaming model. There has been a
vast amount of work on its approximation and parameterized complexity, as will
be discussed shortly.

A matching $M$ in a graph $G$ is a _$k$ -matching_ if $|M|=k$. A _maximum-
weight $k$-matching_ in a weighted graph $G$ is a $k$-matching whose weight is
maximum over all $k$-matchings in $G$. In this paper, we study parameterized
streaming algorithms for the weighted and unweighted $k$-matching problem in
both the dynamic and the insert-only streaming models. In these problems, we
are given a graph stream and a parameter $k\in\mathbb{N}$, and the goal is to
compute a $k$-matching or a maximum-weight $k$-matching. We present results
that improve several results in various aspects and that achieve optimal
complexity upper bounds.

###  1.1 Related Work

Most of the previous works on the graph matching problem in the streaming
model have focused on approximating a maximum matching [1, 5, 6, 13, 15, 17,
21, 25, 26, 28, 29, 31, 32, 37, 42], with the majority of these works
pertaining to the (simpler) insert-only model. The most relevant to ours are
the works of [8, 9, 10, 16], which studied parameterized streaming algorithms
for the maximum matching problem. We survey these works next.

Under the promise that the cardinality of _every_ maximal matching at every
instant of the stream is at most $k$, the authors in [9, 10] presented a one-
pass dynamic streaming algorithm that _w.h.p._ computes a maximal matching in
an unweighted graph stream. Their algorithm runs in $\tilde{O}(k^{2})$ space
and has $\tilde{O}(k^{2})$ update time.

The authors in [8] considered the problem of computing a maximum matching in
the dynamic streaming model. For an unweighted graph $G$, under the promise
that the cardinality of a maximum matching at every instant of the stream is
at most $k$, they presented a sketch-based algorithm that _w.h.p._ computes a
maximum matching of $G$, and that runs in $\tilde{O}(k^{2})$ space and has
$\tilde{O}(1)$ update time. They proved an $\Omega(k^{2})$ lower bound on the
space complexity of any randomized algorithm for the parameterized maximum
matching problem, even in the insert-only model, thus showing that the space
complexity of their algorithm is optimal (modulo a poly-logarithmic factor);
their lower bound result carries over to the $k$-matching problem. They
extended their algorithm to weighted graphs, and presented under the same
promise an algorithm for computing a maximum-weight matching that runs in
space $\tilde{O}(k^{2}W)$ and has $\tilde{O}(1)$ update time, where $W$ is the
number of distinct edge weights.

We remark that the previous work on the weighted matching problem in the
streaming model [8], as well as our current work, assumes that the weight of
each edge remains the same during the stream. Other works on weighted graph
streams make the same assumption [2, 3, 22, 27]. The reason behind this
assumption is that—as shown in this paper, if this assumption is lifted, we
can derive a lower bound on the space complexity of the $k$-matching problem
that is at least linear in the size of the graph, and hence, can be much
larger than the desirable space complexity.

Fafianie and Kratsch [16] studied kernelization streaming algorithms in the
insert-only model for the NP-hard $d$-Set Matching problem (among others),
which for $d=2$, is equivalent to the $k$-matching problem in unweighted
graphs. Their result implies a one-pass kernelization streaming algorithm for
$k$-matching in unweighted graphs that computes a kernel of size
$\mathcal{O}(k^{2}\log k)$, and that runs in $\mathcal{O}(k^{2})$ space and
has $\mathcal{O}(\log k)$ update time.

We mention that Chen et al. [7] studied algorithms for $k$-matching in
unweighted and weighted graphs in the RAM model; their algorithms use limited
computational resources and _w.h.p._ compute a $k$-matching. Clearly, the RAM
model is very different from the streaming model. In order to translate their
algorithm to the streaming model, it would require $\Omega($n$k)$ space and
multiple passes, where $n$ is the number of vertices. However, we mention that
(for the insert-only model), in one of the steps of our algorithm, we were
inspired by a graph operation for constructing a reduced graph, which was
introduced in their paper.

Finally, there has been some work on computing matchings in special graph
classes, and with respect to parameters other than the cardinality of the
matching (e.g., see [30, 34, 35, 36]).

As is commonly the case in the relevant literature, we work under the
assumption that each basic operation on words takes constant time and space.

###  1.2 Results and Techniques

Results and Techniques for the Dynamic Model. We give a one-pass sketch-based
one-sided error streaming algorithm that, for a weighted graph $G$, if $G$
contains a $k$-matching then, with probability at least
$1-\frac{11}{20k^{3}\ln(2k)}$, the algorithm computes a maximum-weight
$k$-matching of $G$ and if $G$ does not contain a $k$-matching then the
algorithm reports that correctly. The algorithm runs in $\tilde{O}(Wk^{2})$
space and has $\tilde{O}(1)$ update time, where $W$ is the number of distinct
weights in the graph. A byproduct of this result is a one-pass one-sided error
streaming algorithm for unweighted $k$-matching running in $\tilde{O}(k^{2})$
space and having $\tilde{O}(1)$ update time. For $k$-matching in unweighted
graphs, the space and update-time complexity of our algorithm are optimal
(modulo a poly-logarithmic factor of $k$).

The above results achieve the same space and update-time complexity as the
results in [8], but generalize them in the following ways. First, our
algorithm can be used to solve the unweighted/weighted $k$-matching problem
for any $k\in\mathbb{N}$, whereas the algorithm in [8] can _only_ be used to
solve the maximum (resp. maximum-weight) matching problem _and_ under the
promise that the given parameter $k$ is at least as large as the cardinality
of every maximum (resp. maximum-weight) matching. In particular, if one wishes
to compute a maximum-weight $k$-matching where $k$ is smaller than the
cardinality of a maximum-weight matching, then the algorithm in [8] cannot be
used or, in the unweighted case, incurs a complexity that depends on the
cardinality of the maximum matching. Second, the correctness of the algorithm
in [8] relies heavily on the promise that the cardinality of every maximum
(resp. maximum-weight) matching is at most $k$, in the sense that, if this
promise is not kept then, for certain instances of the problem, _w.h.p._ the
subgraph returned by the algorithm in [8] does not contain a maximum (resp.
maximum-weight) matching. Third, if we are to work under the same promise as
in [8], which is that the cardinality of every maximum (resp. maximum-weight)
matching is at most $k$, then _w.h.p._ , our algorithm computes a maximum
(resp. maximum-weight) matching. Therefore, in these respects, our results
generalize those in [8].

Another byproduct of our result for weighted $k$-matching is a one-pass
streaming approximation algorithm that, for any $\epsilon>0$, _w.h.p._
computes a $k$-matching that is within a factor of $1+\epsilon$ from a
maximum-weight $k$-matching in $G$; the algorithm runs in
$\tilde{O}(k^{2}\epsilon^{-1}\log W^{\prime})$ space and has $\tilde{O}(1)$
update time, where $W^{\prime}$ is the ratio of the maximum edge-weight to the
minimum edge-weight in $G$. This result matches the approximation result in
[8], which achieves the same bounds, albeit under the aforementioned promise.

We complement the above with a space lower-bound result showing that, if the
restriction that the weight of each edge remains the same during the stream is
lifted, which—as mentioned before–is a standard assumption, then _even_
computing a 1-matching whose weight is within a $(6/5)$-factor from the
maximum-weight 1-matching, by any randomized streaming algorithms requires
space that is at least linear in the size of the graph, and hence, can be much
larger than the desirable space complexity.

As mentioned before, the results in [8] rely on the assumption that the
cardinality of every maximum (resp. maximum-weight) matching is at most $k$.
This assumption is essential for their techniques to work since it is used to
upper bound the number of “large” vertices of degree at least $10k$ by
$\mathcal{O}(k)$, and the number of “small” edges whose both endpoints have
degree at most $10k$ by $\mathcal{O}(k^{2})$. These bounds allow the sampling
of a set of edges that _w.h.p._ contains a maximum (resp. maximum-weight)
matching.

To remove the reliance on the promise, we prove a structural result that can
be useful in its own right for $k$-subset problems (in which the goal is to
compute a $k$-subset with certain prescribed properties from some universe
$U$). Intuitively, the result states that, for any $k$-subset $S\subseteq U$,
_w.h.p._ we can compute $k$ subsets $T_{1},\ldots,T_{k}$ of $U$ that interact
“nicely” with $S$. More specifically, (1) the sets $T_{i}$, for $i\in[k]$, are
pairwise disjoint, (2) $S$ is contained in their union
$\bigcup_{i\in[d]}T_{i}$, and (3) each $T_{i}$ contains exactly one element of
$S$. To prove the theorem, we show that we can randomly choose an
$\mathcal{O}(\log k)$-wise independent hash function that partitions $S$
“evenly”. We then show that we can randomly choose $\mathcal{O}(k/\log
k)$-many hash functions, from a set of universal hash functions, such that
there exist $k$ integers $p_{1},\ldots,p_{k}$, satisfying that $T_{i}$ is the
pre-image of $p_{i}$ under one of the chosen hash functions.

We then apply the above result to obtain the sets $T_{i}$ of vertices that
_w.h.p._ induce the edges of the desired $k$-matching. Afterwards, we use
$\ell_{0}$-sampling to select a smaller subset of edges induced by the
vertices of the $T_{i}$’s that _w.h.p._ contains the desired $k$-matching.
From this smaller subset of edges, a maximum-weight $k$-matching can be
extracted.

Results and Techniques for the Insert-Only Model. We present a one-pass one-
sided error algorithm for computing a maximum-weight $k$-matching that runs in
$\mathcal{O}(k^{2})$ space and has $\mathcal{O}(1)$ update time. The space and
update-time complexity of our algorithm are optimal.

Our techniques rely on partitioning the graph (using hashing), and defining an
auxiliary graph whose vertices are the different parts of the partition; the
auxiliary graph is updated during the stream. By querying this auxiliary
graph, the algorithm can compute a “compact” subgraph of size
$\mathcal{O}(k^{2})$ that, _w.h.p._ , contains the edges of the desired
$k$-matching. A maximum-weight $k$-matching can then be extracted from this
compact subgraph.

Fafianie and Kratsch [16] studied kernelization streaming algorithms in the
insert-only model for the NP-hard $d$-Set Matching problem, which for $d=2$,
is equivalent to $k$-matching in unweighted graphs. Their result implies a
one-pass kernelization streaming algorithm for $k$-matching that computes a
kernel of size $\mathcal{O}(k^{2}\log k)$ bits using $\mathcal{O}(k^{2})$
space and $\mathcal{O}(\log k)$ update time. In comparison, our algorithm
computes a compact subgraph, which is a kernel of the same size as in [16]
(and from which a $k$-matching can be extracted); moreover, our algorithm
treats the more general weighted case, and achieves a better update time of
$\mathcal{O}(1)$ than that of [16], while matching their upper bound on the
space complexity.

##  2 Preliminaries

For a positive integer $i$, let $[i]^{-}$ denote the set of numbers
$\\{0,1,\ldots,i-1\\}$, $[i]$ denote the set of numbers $\\{1,\ldots,i\\}$,
and $\llcorner i\lrcorner$ denote the binary representation of $i$. We write
“u.a.r.” as an abbreviation for “uniformly at random”.

###  2.1 Parameterized Complexity

A _parameterized problem_ $Q$ is a subset of $\Sigma^{*}\times\mathbb{N}$,
where $\Sigma$ is a fixed, finite alphabet. Each instance is a pair $(I,k)$,
where $k\in\mathbb{N}$ is called the parameter. A parameterized problem $Q$ is
_kernelizable_ if there exists a polynomial-time reduction that maps an
instance $(I,k)$ of $Q$ to another instance $(I^{\prime},k^{\prime})$ such
that (1) $k^{\prime}\leq g(k)$ and $|I^{\prime}|\leq g(k)$, where $g$ is a
computable function and $|I^{\prime}|$ is the length of the instance, and
$(2)$ $(I,k)$ is a yes-instance of $Q$ if and only if
$(I^{\prime},k^{\prime})$ is a yes-instance of $Q$. The polynomial-time
reduction is called the _kernelization algorithm_ and the instance
$(I^{\prime},k^{\prime})$ is called the kernel of $(I,k)$. We refer to [14]
for more information.

###  2.2 Graphs and Matching

All graphs discussed in this paper are undirected and simple. Let $G$ be a
graph. We write $V(G)$ and $E(G)$ for the vertex-set and edge-set of $G$,
respectively, and write $uv$ for the edge whose endpoints are $u$ and $v$. A
_matching_ $M\subseteq E(G)$ is a set of edges such that no two distinct edges
in $M$ share the same endpoint. A matching $M$ is a _$k$ -matching_ if
$|M|=k$. A weighted graph $G$ is a graph associated with a weight function
$wt:E(G)\longrightarrow\mathbb{R}$; we denote the weight of an edge $e$ by
$wt(e)$. Let $M$ be a matching in a weighted graph $G$. The weight of $M$,
$wt(M)$, is the sum of the weights of the edges in $M$, that is,
$wt(M)=\sum_{e\in M}wt(e)$. A _maximum-weight $k$-matching_ in a weighted
graph $G$ is a $k$-matching whose weight is maximum over all $k$-matchings in
$G$.

###  2.3 The Graph Streaming Model

A graph _stream_ $\mathcal{S}$ for an underlying graph $G=(V,E)$ is a sequence
of elements, each of the form $(e,op)$, where $op$ is an update to edge $e\in
E(G)$. Each update could be an _insertion_ of an edge, a _deletion_ of an
edge, or in the case of a weighted graph an update to the weight of an edge in
$G$ (and would include the weight of the edge in that case). In the _insert-
only graph streaming_ model, a graph $G=(V,E)$ is given as a stream
$\mathcal{S}$ of elements in which each operation is an edge-insertion, while
in the _dynamic graph streaming_ model a graph $G=(V,E)$ is given as a stream
$\mathcal{S}$ of elements in which the operations could be either edge-
insertions or edge-deletions (with specified weights in case $G$ is weighted).

We assume that the vertex set $V(G)$ contains $n$ vertices, identified with
the integers $\\{0,\ldots,n-1\\}$ for convenience, and that the length of the
stream $\mathcal{S}$ is polynomial in $n$. Therefore, we will treat $v\in V$
as a unique number $v\in[n]^{-}$. Without loss of generality, since the graph
$G$ is undirected, we will assume that the edges of the graph are of the form
$uv$, where $u<v$. Since $G$ can have at most ${n\choose 2}=n(n-1)/2$ edges,
each edge can be represented as a unique number in $[n(n-1)/2]^{-}$. At the
beginning of the stream $\mathcal{S}$, the stream corresponds to a graph with
an empty edge-set. For weighted graphs, we assume that the weight of an edge
is specified when the edge is inserted or deleted.

###  2.4 Computational Model & Problem Definition

In a parameterized graph streaming problem $Q$, we are given an instance of
the form $(\mathcal{S},k)$, where $\mathcal{S}$ is a graph stream of some
underlying graph $G$ and $k\in\mathbb{N}$, and we are queried for a solution
for $(\mathcal{S},k)$ either at the end of $\mathcal{S}$ or after some
arbitrary element/operation in $\mathcal{S}$ [10].

A parameterized streaming algorithm ${\cal A}$ for $Q$ generally uses a
_sketch_ , which is a data structure that supports a set of update operations
[4, 10, 18, 23]. The algorithm ${\cal A}$ can update the sketch after reading
each element of $\mathcal{S}$; the time taken to update the sketch—after
reading an element—is referred to as the _update time_ of the algorithm. The
space used by ${\cal A}$ is the space needed to compute and store the sketch,
and that needed to answer a query on the instance (based on the sketch). The
time complexity of the algorithm is the time taken to extract a solution from
the sketch when answering a query.

We will consider parameterized problems in which we are given a graph stream
$\mathcal{S}$ and $k\in\mathbb{N}$, and the goal is to compute a $k$-matching
or a maximum-weight $k$-matching in $G$ (if one exists). We will consider both
the unweighted and weighted $k$-matching problems, referred to as p-Matching
and p-WT-Matching, respectively, and in both the insert-only and the dynamic
streaming models. For p-WT-Matching, we will follow the standard literature
assumption [8], which is that the weight of every edge remains the same
throughout $\mathcal{S}$; we will consider in Subsection 4.1 a generalized
version of this problem that allows the weight of an edge to change during the
course of stream, and prove lower bound results for this generalization. We
formally define the problems under consideration:

p-Matching
Given: A graph stream $\mathcal{S}$ of an unweighted graph $G$
Parameter: $k$
Goal: Compute a $k$-matching in $G$ or report that no $k$-matching exists

The parameterized Weighted Graph Matching (p-WT-Matching) problem is defined
as fellows:

p-WT-Matching
Given: A graph stream $\mathcal{S}$ of a weighted graph $G$
Parameter: $k$
Goal: Compute a maximum-weight $k$-matching in $G$ or report that no
$k$-matching exists

Clearly, if $k>n/2$ then $G$ does not contain a $k$-matching. Therefore, we
may assume henceforth that $k\leq n/2$.

We will design parameterized streaming algorithms for the above problems. Our
algorithms first extract a subgraph $G^{\prime}$ of the graph stream $G$ such
that _w.h.p._ $G^{\prime}$ contains a $k$-matching or a maximum-weight
$k$-matching of $G$ if and only if $G$ contains one. In the case where the
size of $G^{\prime}$ is a function of $k$, such algorithms are referred to as
_kernelization streaming algorithms_ [8]. We note that result in [8] also
computes a subgraph containing the edges of the maximum (resp. maximum-weight)
matching, without computing the matching itself, as there are efficient
algorithms for extracting a maximum matching (resp. maximum-weight) or a
$k$-matching (resp. maximum-weight $k$-matching) from that subgraph [19, 20,
40].

###  2.5 Probability

For any probabilistic events $E_{1},E_{2},\ldots,E_{r}$, the _union bound_
states that $\Pr(\bigcup_{i=1}^{r}E_{i})\leq\sum_{i=1}^{r}\Pr(E_{i})$. For any
random variables $X_{1},\ldots,X_{r}$ whose expectations are well-defined, the
linearity of expectation states that
$E[\sum_{i=1}^{r}X_{i}]=\sum_{i=1}^{r}E[X_{i}]$, where $E[X_{i}]$ is the
expectation of $X_{i}$. A set of discrete random variables
$\\{X_{1},\ldots,X_{j}\\}$ is called _$\lambda$ -wise independent_ if for any
subset $J\subseteq\\{1,\ldots,j\\}$ with $|J|\leq\lambda$ and for any values
$x_{i}$, we have $\Pr(\wedge_{i\in J}X_{i}=x_{i})=\prod_{i\in
J}\Pr(X_{i}=x_{i})$. A random variable is called a _0-1 random variable_ , if
it only takes one of the two values 0, 1. The following theorem bounds the
tail probability of the sum of 0-1 random variables with limited independence
(see Theorem 2 in [39]):

######  Theorem 2.1.

Given any 0-1 random variables $X_{1},\ldots,X_{j}$, let
$X=\sum_{i=1}^{j}X_{i}$ and $\mu=E[X]$. For any $\delta>0$, if the $X_{i}$’s
are $\lceil\mu\delta\rceil$-wise independent, then

$\Pr(X\geq\mu(1+\delta))\leq\begin{cases}e^{-\mu\delta^{2}/3}&\quad\text{if
}\delta<1\\\ e^{-\mu\delta/3}&\quad\text{if }\delta\geq 1\end{cases}$

###  2.6 $\ell_{0}$-sampler

Let $0<\delta<1$ be a parameter. Let
$\mathcal{S}=(i_{1},\Delta_{1}),\ldots,(i_{p},\Delta_{p}),\ldots$ be a stream
of updates of an underlying vector $\textbf{x}\in\mathbb{R}^{n}$, where
$i_{j}\in[n]$ and $\Delta_{j}\in\mathbb{R}$. The $j$-th update
$(i_{j},\Delta_{j})$ updates the $i_{j}$-th coordinate of x by setting
$\textbf{x}_{i_{j}}=\textbf{x}_{i_{j}}+\Delta_{j}$. An $\ell_{0}$-sampler for
$\textbf{x}\neq 0$ either fails with probability at most $\delta$, or
conditioned on not failing, for any non-zero coordinate $\textbf{x}_{j}$ of x,
returns the pair $(j,\textbf{x}_{j})$ with probability
$\frac{1}{||\textbf{x}||_{0}}$, where $||\textbf{x}||_{0}$ is the
$\ell_{0}$-norm of x, which is the same as the number of non-zero coordinates
of x. For more details, we refer to [12].

Based on the results in [12, 24], and as shown in [8], we can develop a
sketch-based $\ell_{0}$-sampler algorithm for a dynamic graph stream that
samples an edge from the stream. More specifically, the following result was
shown in [8]:

######  Lemma 2.2 (Proof of Theorem 2.1 in [8]).

Let $0<\delta<1$ be a parameter. There exists a linear sketch-based
$\ell_{0}$-sampler algorithm that, given a dynamic graph stream, either
returns FAIL with probability at most $\delta$, or returns an edge chosen
_u.a.r._ amongst the edges of the stream that have been inserted and not
deleted. This $\ell_{0}$-sampler algorithm can be implemented using
$\mathcal{O}(\log^{2}{n}\cdot\log(\delta^{-1}))$ bits of space and
$\tilde{O}(1)$ update time, where $n$ is the number of vertices of the graph
stream.

###  2.7 Hash Functions

Let $U$ be a universe of elements that we will refer to as _keys_. We can
always identify the elements of $U$ with the numbers $0,\ldots,|U|-1$;
therefore, without loss of generality, we will assume henceforth that
$U=\\{0,1,\ldots,|U|-1\\}$. For a set $\mathcal{H}$ of hash functions and a
hash function $h\in\mathcal{H}$, we write $h\in_{u.a.r.}\mathcal{H}$ to denote
that $h$ is chosen _u.a.r._ from $\mathcal{H}$. Let $S\subseteq U$ and $r$ be
a positive integer. A hash function $h:U\longrightarrow[r]^{-}$ is _perfect_
w.r.t. $S$ if it is injective on $S$ (i.e., no two distinct elements $x,y\in
S$ cause a collision).

A set $\mathcal{H}$ of hash functions, each mapping $U$ to $[r]^{-}$, is
called _universal_ if for each pair of distinct keys $x,y\in U$, the number of
hash functions $h\in\mathcal{H}$ for which $h(x)=h(y)$ is at most
$|\mathcal{H}|/r$, or equivalently:

$\Pr_{h\in_{u.a.r.}\mathcal{H}}[h(x)=h(y)]\leq\frac{1}{r}.$

Let $p\geq|U|$ be a prime number. A universal set of hash functions
$\mathcal{H}$ from $U$ to $[r]^{-}$ can be constructed as follows (see chapter
11 in [11]):

$\mathcal{H}=\\{h_{a,b,r}\mid 1\leq a\leq p-1,0\leq b\leq p-1\\},$

where $h_{a,b,r}$ is defined as $h_{a,b,r}(x)=((ax+b)\mod p)\mod r$.

######  Theorem 2.3 (Theorem 11.9 in [11]).

Let $U$ be a universe and $\mathcal{H}$ be a universal set of hash functions,
each mapping $U$ to $[r^{2}]^{-}$. For any set $S$ of $r$ elements in $U$ and
any hash function $h\in_{u.a.r.}\mathcal{H}$, the probability that $h$ is
perfect w.r.t. $S$ is larger than $1/2$.

A set $\mathcal{H}$ of hash functions, each mapping $U$ to $[r]^{-}$, is
called $\kappa$-wise independent if for any $\kappa$ distinct keys
$x_{1},x_{2},...,x_{\kappa}\in U$, and any $\kappa$ (not necessarily distinct)
values $a_{1},a_{2},...,a_{\kappa}\in[r]^{-}$, we have

$\Pr_{h\in_{u.a.r.}\mathcal{H}}[h(x_{1})=a_{1}\wedge
h(x_{2})=a_{2}\wedge\cdots\wedge
h(x_{\kappa})=a_{\kappa}]=\frac{1}{r^{\kappa}}.$

Let $\mathbb{F}$ be a finite field. A $\kappa$-wise independent set
$\mathcal{H}$ of hash functions can be constructed as follows (See
Construction 3.32 in [41]):

$\mathcal{H}=\\{h_{a_{0},a_{1},\ldots,a_{\kappa-1}}:\mathbb{F}\rightarrow\mathbb{F}\\},$

where
$h_{a_{0},a_{1},\ldots,a_{\kappa-1}}(x)=a_{0}+a_{1}x+\cdots+a_{\kappa-1}x^{\kappa-1}$
for $a_{0},\ldots,a_{\kappa-1}\in\mathbb{F}$.

######  Theorem 2.4 (Corollary 3.34 in [41]).

For every $u,d,\kappa\in\mathbb{N}$, there is a family of $\kappa$-wise
independent functions
$\mathcal{H}=\\{h:\\{0,1\\}^{u}\rightarrow\\{0,1\\}^{d}\\}$ such that choosing
a random function from $\mathcal{H}$ takes space
$\mathcal{O}(\kappa\cdot(u+d))$. Moreover, evaluating a function from
$\mathcal{H}$ takes time polynomial in $u,d,\kappa$.

##  3 The Toolkit

In this section, we prove a theorem that can be useful in its own right for
subset problems, that is, problems in which the goal is to compute a
$k$-subset $S$ ($k\in\mathbb{N}$) of some universe $U$ such that $S$ satisfies
certain prescribed properties. Intuitively, the theorem states that, for any
$k$-subset $S\subseteq U$, _w.h.p._ we can compute $k$ subsets
$T_{1},\ldots,T_{k}$ of $U$ that interact “nicely” with $S$. More
specifically, (1) the sets $T_{i}$, for $i\in[k]$, are pairwise disjoint, (2)
$S$ is contained in their union $\bigcup_{i\in[d]}T_{i}$, and (3) each $T_{i}$
contains exactly one element of $S$.

The above theorem will be used in Section 4 to design algorithms for
p-Matching and p-WT-Matching in the dynamic streaming model. Intuitively
speaking, the theorem will be invoked to obtain the sets $T_{i}$ of vertices
that _w.h.p._ induce the edges of the desired $k$-matching; however, these
sets may not necessarily constitute the desired subgraph as they may not have
“small” cardinalities. Sampling techniques will be used to select a smaller
set of edges induced by the vertices of the $T_{i}$’s that _w.h.p._ contains
the edges of the $k$-matching.

To prove this theorem, we proceed in two phases. We give an intuitive
description of these two phases next. We refer to Figure 1 for illustration.

In the first phase, we choose a hashing function $f$ u.a.r. from an
$\mathcal{O}(\ln k)$-wise independent set of hash functions, which hashes $U$
to a set of $d_{1}=\mathcal{O}(k/\ln k)$ integers. We use $f$ to partition the
universe $U$ into $d_{1}$-many subsets $U_{i}$, each consisting of all
elements of $U$ that hash to the same value under $f$. Afterwards, we choose
$d_{1}$ families $F_{0},\ldots,F_{d_{1}-1}$ of hash functions, each containing
$d_{2}=\mathcal{O}(\ln k)$ functions, chosen independently and u.a.r. from a
universal set of hash functions. The family $F_{i}$, $i\in[d_{1}]^{-}$, will
be used restrictively to map the elements of $U_{i}$. Since each family
$F_{i}$ is chosen from a universal set of hash function, for the subset
$S_{i}=S\cap U_{i}$, _w.h.p._ $F_{i}$ contains a hash function $f_{i}$ that is
perfect w.r.t. $S_{i}$; that is, under the function $f_{i}$ the elements of
$S_{i}$ are distinguished. This concludes the first phase of the process,
which is described in Algorithm 1.

$U$$U$$f\in_{u.a.r.}{\mathcal{H}}$$U_{0}$. . .$U_{j-1}$$U_{j}$$U_{j+1}$. .
.$U_{d_{1}-1}$$x$using $h_{1}\in F_{j}$$I_{j\cdot d_{2}}$$I_{j\cdot
d_{2}+1}$using $h_{d_{2}}\in F_{j}$$I_{(j+1)\cdot
d_{2}-1}$$I^{\prime}_{j-1}$$I^{\prime}_{j}$$I^{\prime}_{j+1}$${\mathcal{G}}(x)$

Figure 1: Illustration for Algorithms 1 and 2.

Input: $|U|,k\in\mathbb{N}$ where $|U|>1$
Output: A family of sets of hash functions

1:let $u$ and $d$ be the unique positive integers satisfying $2^{u-1}<|U|\leq
2^{u}$ and $2^{d-1}<\frac{k}{\ln k}\leq 2^{d}$

2:choose $f\in_{u.a.r.}\mathcal{H}$, where
$\mathcal{H}=\\{h:\\{0,1\\}^{u}\rightarrow\\{0,1\\}^{d}\\}$ is a $\lceil 12\ln
k\rceil$-wise independent set of hash functions

3:let $\mathcal{H^{\prime}}$ be a set of universal hash functions from $U$ to
$[\lceil 13\ln k\rceil^{2}]^{-}$

4:let $F_{i}$, for $i\in[2^{d}]^{-}$, be a set of $\lceil 8\ln k\rceil$ hash
functions chosen independently and u.a.r. from $\mathcal{H^{\prime}}$

5:return $\\{f,F_{0},\ldots,F_{2^{d}-1}\\}$

Algorithm 1 : An algorithm for partitioning $U$ and constructing families of
hash functions

In the second phase, we define a relation ${\cal G}$ (from $U$) that, for each
$x\in U$, associates a set ${\cal G}(x)$ of integers. This relation extends
the hash functions in the $F_{j}$’s above by (1) ensuring that elements in
different parts of $U$ (w.r.t. the partitioning) are distinguished, in the
sense that they are associated with subsets of integers that are contained in
disjoint intervals of integers; and (2) maintaining the property that elements
of the same part $U_{j}$ that are distinguished under some function in $F_{j}$
remain so under the extended relation. To do so, for each part $U_{j}$, we
associate an “offset” and create a large gap between any two (consecutive)
offsets; we will ensure that all the elements in the same $U_{j}$ fall within
the same interval determined by two consecutive offsets. To compute the set
${\cal G}(x)$, for an element $x\in U_{j}$, we start with an offset $o_{j}$
that depends solely on $U_{j}$ ($o_{j}=j\cdot d_{2}\cdot d_{3}$ in Algorithm
2), and consider every function in the family $F_{j}$ corresponding to
$U_{j}$. For each such function $h_{i}$, we associate an offset
$o^{\prime}_{i}$ ($o^{\prime}_{i}=(i-1)\cdot d_{3}$ in Algorithm 2), and for
$x$ and that particular function $h_{i}$, we add to ${\cal G}(x)$ the value
$g(j,i,x)=o_{j}+o^{\prime}_{i}+h_{i}(x)$. The above phase is described in
Algorithm 2.

Input: $x\in U$, $k\in\mathbb{N}$, $\\{f,F_{0},\ldots,F_{d_{1}-1}\\}$ is
computed by Algorithm 1, where $|F_{0}|=\cdots=|F_{d_{1}-1}|$
Output: a set ${\cal G}(x)$

1:let $d_{2}=|F_{0}|=\cdots=|F_{d_{1}-1}|$ and $d_{3}=\lceil 13\ln
k\rceil^{2}$

2:${\cal G}(x)=\emptyset$

3:compute $f(\llcorner x\lrcorner)$ and let $j$ be the integer such that
$\llcorner j\lrcorner=f(\llcorner x\lrcorner)$

4:for $i=1$ to $d_{2}$ do

5: let $h_{i}$ be the $i$-th function in $F_{j}$ (assuming an arbitrary
ordering on $F_{j}$)

6: let $g(j,i,x)=j\cdot d_{2}\cdot d_{3}+(i-1)\cdot d_{3}+h_{i}(x)$ and let
${\cal G}(x)={\cal G}(x)\cup\\{g(j,i,x)\\}$

7:return ${\cal G}(x)$

Algorithm 2 : An algorithm that defines the relation ${\cal G}$ from $U$ to
$[d_{1}\cdot d_{2}\cdot d_{3}]^{-}$

Now that the relations ${\cal G}(x)$, for $x\in U$, have been defined, we will
show in the following theorem that, for any $k$-subset $S$ of $U$, _w.h.p._
there exist $k$ distinct elements $i_{0},\ldots,i_{k-1}$, such that their pre-
images ${\cal G}^{-1}(i_{0}),\ldots,{\cal G}^{-1}(i_{k-1})$ are pairwise
disjoint, contain all elements of $S$, and each pre-image contains exactly one
element of $S$; those pre-images serve as the desired sets $T_{i}$, for
$i\in[k]$.

Consider Algorithm 1 and Algorithm 2, and refer to them for the terminologies
used in the subsequent discussions. Let $d_{1}=2^{d}$, $d_{2}=\lceil 8\ln
k\rceil$ and $d_{3}=\lceil 13\ln k\rceil^{2}$ as defined in Algorithms 1 and
2. For $i\in[d_{1}\cdot d_{2}\cdot d_{3}]^{-}$, define $T_{i}=\\{x\in U\mid
i\in{\cal G}(x)\\}$. We define next two sequences of intervals, and prove
certain properties about them, that will be used in the proof of Theorem 3.2.
For $q\in[d_{1}\cdot d_{2}]^{-}$, let $I_{q}=\\{r\mid q\cdot d_{3}\leq
r<(q+1)\cdot d_{3}\\}$. For $t\in[d_{1}]^{-}$, let $I^{\prime}_{t}=\\{r\mid
t\cdot d_{2}\cdot d_{3}\leq r<t\cdot d_{2}\cdot d_{3}+d_{2}\cdot d_{3}\\}$.
Note that each interval $I^{\prime}_{t}$ is partitioned into the $d_{2}$-many
intervals $I_{q}$, for $q=t\cdot d_{2},\ldots,t\cdot d_{2}+d_{2}-1$.

######  Lemma 3.1.

The following statements hold:

  * (A)

For any two distinct integers $a,b\in I_{q}$, where $q\in[d_{1}\cdot
d_{2}]^{-}$, we have $T_{a}\cap T_{b}=\emptyset$.

  * (B)

For $t\in[d_{1}]^{-}$, we have ${\cal G}(U_{t})\subseteq I^{\prime}_{t}$.
Moreover, for any $a\in I^{\prime}_{t},b\in I^{\prime}_{s}$, where $s\neq t$,
we have $T_{a}\cap T_{b}=\emptyset$.

###### Proof.

To prove (A), we proceed by contradiction. Assume that there exists $x\in U$
such that $x\in T_{a}\cap T_{b}$. This implies that both $a$ and $b$ are in
${\cal G}(x)$. Without loss of generality, assume that Algorithm 2 adds $a$ to
${\cal G}(x)$ in iteration $i_{a}$ of Steps 5–6 and adds $b$ in iteration
$i_{b}$, where $i_{a}<i_{b}$. This implies that $a=j\cdot d_{2}\cdot
d_{3}+(i_{a}-1)\cdot d_{3}+h_{i_{a}}(x)$ and $b=j\cdot d_{2}\cdot
d_{3}+(i_{b}-1)\cdot d_{3}+h_{i_{b}}(x)$, where $j$ is the integer such that
$\llcorner j\lrcorner=f(\llcorner x\lrcorner)$. Since $h_{i_{a}}(x)<d_{3}$ and
$h_{i_{b}}(x)<d_{3}$, it follows that $a$ belongs to the interval $I_{j\cdot
d_{2}+i_{a}-1}$ and $b$ belongs to the interval $I_{j\cdot d_{2}+i_{b}-1}$,
which are two distinct intervals (since $i_{a}<i_{b}$), contradicting the
assumption that both $a,b\in I_{q}$.

To prove (B), let $t\in[d_{1}]^{-}$, and let $x\in U_{t}$. The set ${\cal
G}(x)$ consists of the values $g(t,i,x)=t\cdot d_{2}\cdot d_{3}+(i-1)\cdot
d_{3}+h_{i}(x)$, for $i=1,\ldots,d_{2}$. Since $0\leq h_{i}(x)<d_{3}$ for any
$i\in[d_{2}]$ and any $x\in U$, it follows that $t\cdot d_{2}\cdot d_{3}\leq
g(t,i,x)\leq t\cdot d_{2}\cdot d_{3}+(d_{2}-1)\cdot d_{3}+d_{3}-1<t\cdot
d_{2}\cdot d_{3}+d_{2}\cdot d_{3}$, and hence, $g(t,i,x)\in I^{\prime}_{t}$.
This proves that ${\cal G}(U_{t})\subseteq I^{\prime}_{t}$.

To prove that, for any $a\in I^{\prime}_{t},b\in I^{\prime}_{s}$, where $s\neq
t$, we have $T_{a}\cap T_{b}=\emptyset$, suppose not and let $x\in T_{a}\cap
T_{b}$. By the first part of the claim, we have $a\in{\cal G}(x)\subseteq
I^{\prime}_{t}$ and $b\in{\cal G}(x)\subseteq I^{\prime}_{s}$, which is a
contradiction since $I^{\prime}_{t}\cap I^{\prime}_{s}=\emptyset$. ∎

######  Theorem 3.2.

For any subset $S\subseteq U$ of cardinality $k\geq 2$, with probability at
least $1-\frac{4}{k^{3}\ln k}$, there exist $k$ sets
$T_{i_{0}},\ldots,T_{i_{k-1}}$ such that: (1) $|T_{i_{j}}\cap S|=1$ for
$j\in[k]^{-}$, (2) $S\subseteq\cup_{j\in[k]^{-}}T_{i_{j}}$, and (3)
$T_{i_{j}}\cap T_{i_{l}}=\emptyset$ for $j\neq l\in[k]^{-}$.

###### Proof.

For $j\in[d_{1}]^{-}$, let $U_{j}$ be the set of elements in $U$ whose image
is $\llcorner j\lrcorner$ under $f$ (defined in Step 2 of Algorithm 1), that
is $U_{j}=\\{y\in U\mid f(\llcorner y\lrcorner)=\llcorner j\lrcorner\\}$.
Clearly, the sets $U_{j}$, for $j\in[d_{1}]^{-}$, partition the universe $U$.
We will show that, with probability at least $1-\frac{4}{k^{3}\ln k}$, there
exist $k$ sets $T_{i_{0}},\ldots,T_{i_{k-1}}$ that satisfy conditions (1)–(3)
in the statement of the theorem.

Let $S\subseteq U$ be any subset such that $|S|=k$. For $j\in[d_{1}]^{-}$ and
$y\in S$, let $X_{y,j}$ be the random variable defined as $X_{y,j}=1$ if
$f(\llcorner y\lrcorner)=\llcorner j\lrcorner$ and 0 otherwise. Let
$X_{j}=\sum_{y\in S}X_{y,j}$, and $S_{j}=\\{y\in S\mid f(\llcorner
y\lrcorner)=\llcorner j\lrcorner\\}$. Thus, $|S_{j}|=X_{j}$. Since $f$ is
$\lceil 12\ln k\rceil$-wise independent, the random variables $X_{y,j}$, for
$y\in S$, are $\lceil 12\ln k\rceil$-wise independent and
$\Pr(X_{y,j}=1)=\frac{1}{d_{1}}$. Thus, $E[X_{j}]=|S|\cdot\frac{1}{d_{1}}$.
Since $d_{1}=2^{d}$ and $2^{d-1}<\frac{k}{\ln k}\leq 2^{d}$ by definition, we
have $\frac{k}{\ln k}\leq d_{1}<\frac{2k}{\ln k}$ and $\frac{\ln
k}{2}<E[X_{j}]\leq\ln k$. Applying Theorem 2.1 with $\mu=E[X_{j}]$ and
$\delta=\frac{12\ln k}{E[X_{j}]}>1$, we get
$\Pr(X_{j}\geq(1+\delta)E[X_{j}])\leq e^{-E[X_{j}]\delta/3}=\frac{1}{k^{4}}$.
Since $E[X_{j}]\leq\ln k$ and $\delta=\frac{12\ln k}{E[X_{j}]}$, we have
$(1+\delta)E[X_{j}]\leq 13\ln k$. Hence, $\Pr(X_{j}\geq 13\ln
k)\leq\Pr(X_{j}\geq(1+\delta)E[X_{j}])\leq\frac{1}{k^{4}}$. Let $\mathcal{E}$
denote the event that $\bigwedge_{i\in[d_{1}]^{-}}(X_{i}\leq 13\ln k)$. By the
union bound, we have $\Pr(\mathcal{E})\geq 1-\frac{d_{1}}{k^{4}}\geq
1-\frac{2}{k^{3}\ln k}$, where the last inequality holds since
$d_{1}<2k/\ln{k}$.

Assume that event $\mathcal{E}$ occurs, i.e., that $|S_{j}|\leq 13\ln k$ holds
for $j\in[d_{1}]^{-}$. Consider Step 4 in Algorithm 1. Fix $j\in[d_{1}]^{-}$,
and let $E_{j}$ be the event that $F_{j}$ does not contain any perfect hash
function w.r.t. $S_{j}$. Let $h$ be a hash function picked from
$\mathcal{H^{\prime}}$ u.a.r. Since $|S_{j}|\leq 13\ln k$ (by assumption), by
Theorem 2.3, with probability at least $1/2$, $h$ is perfect w.r.t. $S_{j}$.
Since $F_{j}$ consists of $\lceil 8\ln k\rceil$ hash functions chosen
independently and u.a.r. from $\mathcal{H^{\prime}}$, we have
$\Pr(E_{j})\leq(1/2)^{\lceil 8\ln k\rceil}<\frac{1}{k^{4}}$. Applying the
union bound, we have
$\Pr(\cup_{j\in[d_{1}]^{-}}E_{j})\leq\frac{d_{1}}{k^{4}}<\frac{2}{k^{3}\ln
k}$. Let $\mathcal{E}^{\prime}$ be the event that there exist $d_{1}$
functions $f_{0},f_{1},\ldots,f_{d_{1}-1}$ such that $f_{j}\in F_{j}$ and
$f_{j}$ is perfect w.r.t. $S_{j}$, $j\in[d_{1}]^{-}$. Therefore,
$\Pr(\mathcal{E}^{\prime})\geq\Pr(\mathcal{E})(1-\Pr(\cup_{j\in[d_{1}]^{-}}E_{j}))\geq
1-\frac{4}{k^{3}\ln k}+\frac{4}{k^{6}\ln^{2}k}\geq 1-\frac{4}{k^{3}\ln k}$.
Suppose that such a set $\\{f_{0},\ldots,f_{d_{1}-1}\\}$ of functions exists.
Let $\eta(q)$ be the iteration number $i$ in Step 5 of Algorithm 2 during
which $f_{q}\in F_{q}$ is chosen, for $q\in[d_{1}]^{-}$. We define the
following (multi-)set $B$ as follows. For each $q\in[d_{1}]^{-}$, and for
element $x\in S_{q}$, add to $B$ the element $g(q,\eta(q),x))$ defined in
Steps 5–6 of Algorithm 2 (by $\\{f,f_{0},\ldots,f_{k-1}\\}$). Observe that, by
the definition of $B$, for every $x\in S$, there exists $a\in B$ such that
$x\in T_{a}$. We will show next that $B$ contains exactly $k$ distinct
elements, and that, for any $a\neq b\in B$, it holds that $T_{a}\cap
T_{b}=\emptyset$. The above will show that the sets $\\{T_{a}\mid a\in B\\}$
satisfy conditions (1)–(3) of the theorem, thus proving the theorem.

It suffices to show that for any two distinct elements of $S$, the
corresponding elements added to $B$ are distinct. Let $x_{1}$ and $x_{2}$ be
two distinct elements of $S$. Assume that $x_{1}\in S_{j}$ and $x_{2}\in
S_{l}$, where $j,l\in[d_{1}]^{-}$. We distinguish two cases based on whether
or not $j=l$.

If $j=l$, we have $g(j,\eta(j),x_{1})=j\cdot d_{2}\cdot d_{3}+(\eta(j)-1)\cdot
d_{3}+f_{j}(x_{1})$ and $g(j,\eta(j),x_{2})=j\cdot d_{2}\cdot
d_{3}+(\eta(j)-1)\cdot d_{3}+f_{j}(x_{2})$. Since $f_{j}$ is perfect w.r.t.
$S_{j}$, we have $g(j,\eta(j),x_{1})\neq g(j,\eta(j),x_{2})$. Moreover, both
$g(j,\eta(j),x_{1})$ and $g(j,\eta(j),x_{2})$ are in $I_{j\cdot
d_{2}+(\eta(j)-1)}$ (since $0\leq h_{j}(x_{1}),h_{j}(x_{2})<d_{3}$), where
$j\cdot d_{2}+(\eta(j)-1)\leq(d_{1}-1)\cdot d_{2}+(d_{2}-1)\in[d_{1}\cdot
d_{2}]^{-}$. By part (A) of Lemma 3.1, it holds that
$T_{g(j,\eta(j),x_{1})}\cap T_{g(j,\eta(j),x_{2})}=\emptyset$.

Suppose now that $j\neq l$. By definition of $S_{j},S_{l},U_{j},U_{l}$, we
have $S_{j}\subseteq U_{j}$ and $S_{l}\subseteq U_{l}$. Consequently,
$g(j,\eta(j),x_{1})\in{\cal G}(U_{j})$ and $g(l,\eta(l),x_{2})\in{\cal
G}(U_{l})$ hold. By part (B) of Lemma 3.1, we have ${\cal G}(U_{j})\subseteq
I^{\prime}_{j}$ and ${\cal G}(U_{l})\subseteq I^{\prime}_{l}$. Therefore,
$g(j,\eta(j),x_{1})\neq g(l,\eta(l),x_{2})$. Moreover,
$T_{g(j,\eta(j),x_{1})}\cap T_{g(l,\eta(l),x_{2})}=\emptyset$ holds by part
(B) of Lemma 3.1 as well. ∎

######  Theorem 3.3.

Algorithm 1 runs in space $\mathcal{O}(k+(\log k)(\log|U|))$, and Algorithm 2
runs in space $\mathcal{O}(\log k)$ and in time polynomial in $\log|U|$.

###### Proof.

In Algorithm 1, since $f$ is $\lceil 12\ln k\rceil$-wise independent, storing
$f$ uses space $\mathcal{O}(\ln k\cdot\max\\{u,d\\})=\mathcal{O}((\log
k)(\log|U|))$ (since $k\leq|U|$) by Theorem 2.4. Storing a universal hash
function uses $\mathcal{O}(1)$ space, and thus storing
$\\{F_{0},\ldots,F_{d_{1}-1}\\}$ uses $\mathcal{O}(d_{1}\cdot
d_{2})=\mathcal{O}(k)$ space. Therefore, Algorithm 1 can be implemented in
space $\mathcal{O}(k+(\log k)(\log|U|))$.

For Algorithm 2, since ${\cal G}(x)$ contains exactly $d_{2}$ elements,
storing ${\cal G}(x)$ takes $\mathcal{O}(d_{2})=\mathcal{O}(\ln k)$ space. In
Step 3, computing $f(\llcorner x\lrcorner)$ takes time polynomial in $\log|U|$
and $\log k$ by Theorem 2.4, since $f$ is a $\lceil 12\ln k\rceil$-wise
independent hash function from $\\{0,1\\}^{u}$ to $\\{0,1\\}^{d}$. Computing
$j$ in Step 3 takes time polynomial in $d=\mathcal{O}(\log k)$ since
$f(\llcorner x\lrcorner)\in\\{0,1\\}^{d}$. Therefore, Step 3 can be performed
in time polynomial in $\log|U|$ and $\log k$, and hence polynomial in
$\log|U|$ (since $k\leq|U|$). Step 6 can be implemented in time polynomial in
$\log k$, since $|F_{j}|=\lceil 8\ln k\rceil$. Altogether, Algorithm 2 takes
time polynomial in $\log|U|$. This completes the proof. ∎

##  4 Dynamic Streaming Model

In this section, we present results on p-Matching and p-WT-Matching in the
dynamic streaming model. The algorithm uses the toolkit developed in the
previous section, together with the $\ell_{0}$-sampling technique discussed in
Section 2. We first give a high-level description of how the algorithm works.

We will hash the vertices of the graph to a range $R$ of size
$\mathcal{O}(k\log^{2}k)$. For each element $(e=uv,wt(e),op)\in\mathcal{S}$,
we use the relation ${\cal G}$, discussed in Section 3, and compute the two
sets ${\cal G}(u)$ and ${\cal G}(v)$. For each $i\in{\cal G}(u)$ and each
$j\in{\cal G}(v)$, we associate an instance of an $\ell_{0}$-sampler
primitive, call it ${\mathscr{C}}_{i,j,wt(uv)}$, and update it according to
the operation $op$. Recall that it is assumed that the weight of every edge
does not change throughout the stream.

The solution computed by the algorithm consists of a set of edges created by
invoking each of the $\tilde{O}(Wk^{2})$ $\ell_{0}$-sampler algorithms to
sample at most one edge from each ${\mathscr{C}}_{i,j,w}$, for each pair of
$i,j$ in the range $R$ and each edge-weight of the graph stream.

The intuition behind the above algorithm (i.e., why it achieves the desired
goal) is the following. Suppose that there exists a maximum-weight
$k$-matching $M$ in $G$, and let $M=\\{u_{0}u_{1},\ldots,u_{2k-2}u_{2k-1}\\}$.
By Theorem 3.2, _w.h.p._ there exist $i_{0},\ldots,i_{2k-1}$ in the range $R$
such that $u_{j}\in T_{i_{j}}$, for $j\in[2k-1]^{-}$, and such that the
$T_{i_{j}}$’s are pairwise disjoint. Consider the $k$ $\ell_{0}$-samplers
$\mathscr{C}_{i_{2j},i_{2j+1},wt(u_{2j}u_{2j+1})}$, where $j\in[k]^{-}$. Then,
_w.h.p._ , the $k$ edges sampled from these $k$ $\ell_{0}$-samplers are the
edges of a maximum-weight $k$-matching (since the $T_{i_{j}}$’s are pairwise
disjoint) whose weight equals that of $M$.

Algorithm 3 The streaming algorithm $\mathcal{A}_{dynamic}$ in the dynamic
streaming model

1:

2:$\mathcal{A}_{dynamic}$-Preprocess: The preprocessing algorithm

3:

4:$n=|V(G)|$ and a parameter $k\in\mathbb{N}$

5:let $\mathscr{C}$ be a set of $\ell_{0}$-sampling primitive instances and
$\mathscr{C}=\emptyset$

6:let $\\{f,F_{0},F_{1},\ldots,$ $F_{d_{1}-1}\\}$ be the output of Algorithm 1
on input $(n,2k)$

7:

8:$\mathcal{A}_{dynamic}$-Update: The update algorithm

9:

10:The $i$-th update $(e_{i}=uv,wt(e),op)\in\mathcal{S}$

1:let ${\cal G}(u)$ be the output of Algorithm 2 on input
($u,2k,\\{f,F_{0},F_{1},\ldots,F_{d_{1}-1}\\}$)

2:let ${\cal G}(v)$ be the output of Algorithm 2 on input
($v,2k,\\{f,F_{0},F_{1},\ldots,F_{d_{1}-1}\\}$)

3:for $i\in{\cal G}(u)$ and $j\in{\cal G}(v)$ do

4: if $\mathscr{C}_{i,j,wt(uv)}\notin\mathscr{C}$ then

5: create the $\ell_{0}$-sampler $\mathscr{C}_{i,j,wt(uv)}$

6: feed $\langle uv,op\rangle$ to the $\ell_{0}$-sampling algorithm
$\mathscr{C}_{i,j,wt(uv)}$ with parameter $\delta$

7:

8:$\mathcal{A}_{dynamic}$-Query: The query algorithm after the $i$-th update

9:

1:let $E^{\prime}=\emptyset$

2:for each $\mathscr{C}_{i,j,w}\in\mathscr{C}$ do

3: apply the $\ell_{0}$-sampler $\mathscr{C}_{i,j,w}$ with parameter $\delta$
to sample an edge $e$

4: if $\mathscr{C}_{i,j,w}$ does not FAIL then set
$E^{\prime}=E^{\prime}\cup\\{e\\}$

5:return a maximum-weight $k$-matching in
$G^{\prime}=(V(E^{\prime}),E^{\prime})$ if any; otherwise, return $\emptyset$

Let $\mathcal{S}$ be a graph stream of a weighted graph $G=(V,E)$ with $W$
distinct weights, where $W\in\mathbb{N}$, and let $n=|V|$ and
$k\in\mathbb{N}$. Choose $\delta=\frac{1}{20k^{4}\ln(2k)}$. Let ${\cal
A}_{dynamic}$ be the algorithm consisting of the sequence of three
subroutines/algorithms $\mathcal{A}_{dynamic}$-Preprocess,
$\mathcal{A}_{dynamic}$-Update, and $\mathcal{A}_{dynamic}$-Query, where
$\mathcal{A}_{dynamic}$-Preprocess is applied at the beginning of the stream,
$\mathcal{A}_{dynamic}$-Update is applied after each operation, and
$\mathcal{A}_{dynamic}$-Query is applied whenever the algorithm is queried for
a solution after some update operation. Without loss of generality, and for
convenience, we will assume that the algorithm is queried at the end of the
stream $\mathcal{S}$, even though the query could take place after any
arbitrary operation.

######  Lemma 4.1.

Let $M^{\prime}$ be the matching obtained by applying the algorithm ${\cal
A}_{dynamic}$ with $\mathcal{A}_{dynamic}$-Query invoked at the end of
$\mathcal{S}$. If $G$ contains a $k$-matching then, with probability at least
$1-\frac{11}{20k^{3}\ln(2k)}$, $M^{\prime}$ is a maximum-weight $k$-matching
of $G$.

###### Proof.

Suppose that $G$ has a $k$-matching, and let
$M=\\{u_{0}u_{1},\ldots,u_{2k-2}u_{2k-1}\\}$ be a maximum-weight $k$-matching
in $G$. (Note that we can assume that $u_{2j}<u_{2j+1}$ for every
$j\in[k]^{-}$; see Section 2.) From Algorithm 1 and Algorithm 2, it follows
that $d_{1}=O(\frac{k}{\ln k})$, $d_{2}=O(\ln k)$, and $d_{3}=O(\ln^{2}k)$.
For $i\in[d_{1}\cdot d_{2}\cdot d_{3}]^{-}$, let $T_{i}=\\{u\in V\mid
i\in{\cal G}(u)\\}$. By Theorem 3.2, with probability at least
$1-\frac{4}{(2k)^{3}\ln(2k)}=1-\frac{1}{2k^{3}\ln(2k)}$, there exist
$i_{0},i_{1},\ldots,i_{2k-1}$ such that (1) $u_{j}\in T_{i_{j}},j\in[2k]^{-}$,
and (2) $T_{i_{j}}\cap T_{i_{l}}=\emptyset$ for $j\neq l\in[2k]^{-}$. Let
$\mathcal{E^{\prime}}$ be the above event. Then $\Pr(\mathcal{E^{\prime}})\geq
1-\frac{1}{2k^{3}\ln(2k)}$. By Step 6 of $\mathcal{A}_{dynamic}$-Update,
$u_{2j}u_{2j+1}$ will be fed into
$\mathscr{C}_{i_{2j},i_{2j+1},wt(u_{2j}u_{2j+1})}$ for $j\in[k]^{-}$. Hence,
$\mathscr{C}_{i_{2j},i_{2j+1},wt(u_{2j}u_{2j+1})}$ is fed at least one edge
for every $j\in[k]^{-}$.

Now, let us compute the sampling success probability in Step 4 of
$\mathcal{A}_{dynamic}$-Query. Note that this probability involves both Step 6
of $\mathcal{A}_{dynamic}$-Update and Step 4 of $\mathcal{A}_{dynamic}$-Query.
In Step 6 of $\mathcal{A}_{dynamic}$-Update and Step 4 of
$\mathcal{A}_{dynamic}$-Query, we employ the $\ell_{0}$-sampling primitive in
Lemma 2.2. Let $\mathcal{E}$ be the event that one edge is sampled
successfully for each $\ell_{0}$-sampler in
$\\{\mathscr{C}_{i_{2j},i_{2j+1},wt(u_{2j}u_{2j+1})}\mid j\in[k]^{-}\\}$. By
Lemma 2.2, one $\ell_{0}$-sampler fails with probability at most $\delta$.
Hence, $\Pr(\mathcal{E})\geq 1-k\cdot\delta$ by the union bound. Since
$\delta=\frac{1}{20k^{4}\ln(2k)}$, we get $\Pr(\mathcal{E})\geq
1-\frac{1}{20k^{3}\ln(2k)}$. Hence, with probability at least
$1-\frac{1}{20k^{3}\ln(2k)}$, $E^{\prime}$ will contain one edge $e_{j}$
sampled from $\mathscr{C}_{i_{2j},i_{2j+1},wt(u_{2j}u_{2j+1})}$ for each
$j\in[k]^{-}$. Note that $e_{j}$ may be $u_{2j}u_{2j+1}$ or any other edge
with the same weight as $u_{2j}u_{2j+1}$. Since $T_{i_{j}}\cap
T_{i_{l}}=\emptyset$ for every $j\neq l\in[2k]^{-}$, we have that the edges
fed to $\mathscr{C}_{i_{2a},i_{2a+1},wt(u_{2a}u_{2a+1})}$ and
$\mathscr{C}_{i_{2b},i_{2b+1},wt(u_{2b}u_{2b+1})}$ are vertex disjoint, for
all $a\neq b\in[k]^{-}$. Thus, $\\{e_{0},\ldots,e_{k-1}\\}$ forms a maximum-
weight $k$-matching of $G$. Applying the union bound, the probability that the
graph $G^{\prime}$ contains a maximum-weight $k$-matching of $G$ is at least
$1-\Pr(\bar{\mathcal{E}}\cup\bar{\mathcal{E^{\prime}}})\geq$
$1-\Pr(\bar{\mathcal{E^{\prime}}})-\Pr(\bar{\mathcal{E}})\geq
1-\frac{1}{2k^{3}\ln(2k)}-\frac{1}{20k^{3}\ln(2k)}=1-\frac{11}{20k^{3}\ln(2k)}$.
Since $M^{\prime}$ is a maximum-weight $k$-matching of $G^{\prime}$,
$M^{\prime}$ is a maximum-weight $k$-matching of $G$ as well. ∎

######  Theorem 4.2.

The algorithm ${\cal A}_{dynamic}$ outputs a matching $M^{\prime}$ such that
(1) if $G$ contains a $k$-matching then, with probability at least
$1-\frac{11}{20k^{3}\ln(2k)}$, $M^{\prime}$ is a maximum-weight $k$-matching
of $G$; and (2) if $G$ does not contain a $k$-matching then
$M^{\prime}=\emptyset$. Moreover, the algorithm ${\cal A}_{dynamic}$ runs in
$\tilde{O}(Wk^{2})$ space and has $\tilde{O}(1)$ update time.

###### Proof.

First, observe that $G^{\prime}$ is a subgraph of $G$, since it consists of
edges sampled from subsets of edges in $G$. Therefore, statement (2) in the
theorem clearly holds true. Statement (1) follows from Lemma 4.1. Next, we
analyze the update time of algorithm ${\cal A}_{dynamic}$.

From Algorithm 1 and Algorithm 2, we have $d_{1}=O(\frac{k}{\ln k})$,
$d_{2}=O(\ln k)$, $d_{3}=O(\ln^{2}k)$ and $|F_{i}|=O(\ln k)$ for
$i\in[d_{1}]^{-}$. Thus, $|{\cal G}(u)|=O(\ln k)$ holds for all $u\in V$. For
the update time, it suffices to examine Steps 1–6 of
$\mathcal{A}_{dynamic}$-Update. By Theorem 3.3, Steps 1–2 take time polynomial
in $\log n$, which is $\tilde{O}(1)$. For Step 4, we can index $\mathscr{C}$
using a sorted sequence of triplets $(i,j,w)$, where $i,j\in[d_{1}\cdot
d_{2}\cdot d_{3}]^{-}$ and $w$ ranges over all possible weights. Since
$d_{1}=\mathcal{O}(\frac{k}{\ln k})$, $d_{2}=\mathcal{O}(\ln k)$ and
$d_{3}=\mathcal{O}(\ln^{2}k)$, we have $|\mathscr{C}|=\mathcal{O}((d_{1}\cdot
d_{2}\cdot d_{3})^{2}\cdot W)=\mathcal{O}(Wk^{2}\ln^{4}k)$. Using binary
search on $\mathscr{C}$, one execution of Step 4 takes time $\mathcal{O}(\log
W+\log k)$. Since $|{\cal G}(u)|=O(\ln k)$ for every $u\in V$, and since by
Lemma 2.2 updating the sketch for an $\ell_{0}$-sampler takes
$\tilde{\mathcal{O}{}}(1)$ time, Steps 3–6 take time
$\mathcal{O}(\ln^{2}k)\cdot(\mathcal{O}(\log W+\log
k)+\tilde{O}(1))=\tilde{O}(1)$. Therefore, the overall update time is
$\tilde{O}(1)$.

Now, we analyze the space complexity of the algorithm. First, consider
$\mathcal{A}_{dynamic}$-Preprocess. Obviously, Step 5 uses $\mathcal{O}(1)$
space. Steps 5–6 use space $\mathcal{O}(k+(\log k)(\log n))$ (including the
space used to store $\\{f,F_{0},\ldots,F_{d_{1}-1},\mathscr{C}\\}$) by Theorem
3.3. Altogether, $\mathcal{A}_{dynamic}$-Preprocess runs in space
$\mathcal{O}(k+(\log k)(\log n))$. Next, we discuss
$\mathcal{A}_{dynamic}$-Update. Steps 1–2 take space $O(\ln k)$ by Theorem
3.3. Observe that the space used in Steps 3–6 is dominated by the space used
by the set $\mathscr{C}$ of $\ell_{0}$-sampling primitive instances. By Lemma
2.2, one instance of an $\ell_{0}$-sampling primitive uses space
$\mathcal{O}(\log^{2}n\cdot\log(\delta^{-1}))$. Since
$\delta=\frac{1}{20k^{4}\ln(2k)}$, we have $\log(\delta^{-1})=\mathcal{O}(\log
k)$. It follows that a single instance of an $\ell_{0}$-sampler uses space
$\mathcal{O}(\log^{2}n\cdot\log k)$. Since
$|\mathscr{C}|=\mathcal{O}(Wk^{2}\ln^{4}k)$, Steps 3–6 use space
$\mathcal{O}(Wk^{2}\log^{2}n\log^{5}k)=\tilde{\mathcal{O}}(Wk^{2})$. Finally,
consider ${\cal A}_{dynamic}$-Query. The space in Steps 1 – 4 is dominated by
the space used by $\mathscr{C}$ and the space needed to store the graph
$G^{\prime}$, and hence $E^{\prime}$. By the above discussion, $\mathscr{C}$
takes space $\tilde{\mathcal{O}}(Wk^{2})$. Since at most one edge is sampled
from each $\ell_{0}$-sampler instance and
$|\mathscr{C}|=\mathcal{O}(Wk^{2}\ln^{4}k)$, we have
$|E^{\prime}|=|\mathscr{C}|=\mathcal{O}(Wk^{2}\ln^{4}k)$. Step 5 utilizes
space $\mathcal{O}(|E^{\prime}|)$ [19, 20]. Therefore, ${\cal
A}_{dynamic}$-Query runs in space $\tilde{\mathcal{O}}(Wk^{2})$. It follows
that the space complexity of $\mathcal{A}_{dynamic}$ is
$\tilde{\mathcal{O}}(Wk^{2})$. ∎

The space complexity of the above algorithm is large if the number of distinct
weights $W$ is large. Under the same promise that the parameter $k$ is at
least as large as the size of any maximum matching in $G$, an approximation
scheme for p-WT-Matching that is more space efficient was presented in [8].
This scheme approximates p-WT-Matching to within ratio $1+\epsilon$, for any
$\epsilon>0$, and has space complexity $\tilde{O}(k^{2}\epsilon^{-1}\log
W^{\prime})$ and update time $\tilde{O}(1)$. The main idea behind this
approximation scheme is to reduce the number of distinct weights in $G$ by
rounding each weight to the nearest power of $1+\epsilon$.

Using Theorem 4.2, and following the same approach in [8], we can obtain the
same approximation result as in [8], albeit without the reliance on such a
strong promise:

######  Theorem 4.3.

Let $\mathcal{S}$ be a graph stream of a graph $G$, and let
$W^{\prime}=wt(e)/wt(e^{\prime})$, where $e\in E(G)$ is an edge with the
maximum weight and $e^{\prime}\in E(G)$ is an edge with the minimum weight.
Let $0<\epsilon<1$. In the dynamic streaming model, there exists an algorithm
for p-WT-Matching that computes a matching $M^{\prime}$ such that (1) if $G$
contains a maximum-weight $k$-matching $M$, then with probability at least
$1-\frac{11}{20k^{3}\ln(2k)}$, $wt(M^{\prime})>(1-\epsilon)wt(M)$; and (2) if
$G$ does not contain a $k$-matching then $M^{\prime}=\emptyset$. Moreover, the
algorithm runs in $\tilde{O}(k^{2}\epsilon^{-1}\log W^{\prime})$ space and has
$\tilde{O}(1)$ update time.

###### Proof.

For each edge $e\in E$, round $wt(e)$ and assign it a new weight of
$(1+\epsilon)^{i}$ such that $(1+\epsilon)^{i-1}<wt(e)\leq(1+\epsilon)^{i}$.
Thus, there are $\mathcal{O}(\epsilon^{-1}\log W^{\prime})$ distinct weights
after rounding. By Theorem 4.2, the space and update time are
$\tilde{\mathcal{O}}(k^{2}\epsilon^{-1}\log W^{\prime})$ and
$\tilde{\mathcal{O}}(1)$ respectively, and the success probability is at least
$1-\frac{11}{20k^{3}\ln(2k)}$. Now we prove that
$wt(M^{\prime})>(1-\epsilon)wt(M)$.

Let $e\in M$ and let $e^{\prime}$ be the edge sampled from the
$\ell_{0}$-sampler that $e$ is fed to. It suffices to prove that
$wt(e^{\prime})>(1-\epsilon)wt(e)$. Assume that $wt(e)$ is rounded to
$(1+\epsilon)^{i}$. Then, $wt(e^{\prime})$ is rounded to $(1+\epsilon)^{i}$ as
well. If $wt(e^{\prime})\geq wt(e)$, we are done; otherwise,
$(1+\epsilon)^{i-1}<wt(e^{\prime})<wt(e)\leq(1+\epsilon)^{i}$. It follows that
$wt(e^{\prime})>(1+\epsilon)^{i-1}\geq wt(e)/(1+\epsilon)>(1-\epsilon)wt(e)$.
∎

The following theorem is a consequence of Theorem 4.2 (applied with $W=1$):

######  Theorem 4.4.

In the dynamic streaming model, there is an algorithm for p-Matching such
that, on input $(\mathcal{S},k)$, the algorithm outputs a matching
$M^{\prime}$ satisfying that (1) if $G$ contains a $k$-matching then, with
probability at least $1-\frac{11}{20k^{3}\ln(2k)}$, $M^{\prime}$ is a
$k$-matching of $G$; and (2) if $G$ does not contain a $k$-matching then
$M^{\prime}=\emptyset$. Moreover, the algorithm runs in
$\tilde{\mathcal{O}}(k^{2})$ space and has $\tilde{\mathcal{O}}(1)$ update
time.

###  4.1 Lower Bound

Consider an undirected graphs $G=(V,E)$ with a weight function
$wt:E(G)\longrightarrow\mathbb{R}_{\geq 0}$. We define a more general dynamic
graph streaming model for an undirected graph $G$: $G$ is given as a stream
$\mathcal{S}=(e_{i_{1}},\Delta_{1}(e_{i_{1}})),\ldots,(e_{i_{j}},\Delta_{j}(e_{i_{j}})),\ldots$
of updates of the weights of the edges, where $e_{i_{j}}$ is an edge and
$\Delta_{j}(e_{i_{j}})\in\mathbb{R}$, and a parameter $k\in\mathbb{N}$. The
$j$-th update $(e_{i_{j}},\Delta_{j}(e_{i_{j}}))$ updates the weight of
$e_{i_{j}}$ by setting $wt(e_{i_{j}})=wt(e_{i_{j}})+\Delta_{j}(e_{i_{j}})$. We
assume that $wt(\cdot)\geq 0$ for every update $j$. Initially,
$wt(\cdot)=\textbf{0}$. This models allows the weight of an edge to
dynamically change, and generalizes the dynamic graph streaming model in [8],
where $wt(e)$ is either $0$ or a fixed value associated with $e$. In
particular, each element $(e_{i_{j}},\Delta_{j}(e_{i_{j}}))$ in $\mathcal{S}$
is either $(e_{i_{j}},wt(e_{i_{j}}))$ or $(e_{i_{j}},-wt(e_{i_{j}}))$, and
$(e_{i_{j}},wt(e_{i_{j}}))$ means to insert the edge $e_{i_{j}}$ while
$(e_{i_{j}},-wt(e_{i_{j}}))$ represents the deletion of the edge $e_{i_{j}}$.

In this subsection, we prove a lower bound for the weighted $k$-matching
problem in the more general dynamic streaming model. This lower bound result
holds _even_ for parameter value $k=1$. We prove this lower bound via a
reduction from the problem of computing the function $F_{\infty}$ of data
streams defined as follows:

Given a data stream $\mathcal{S}^{\prime}=x_{1},x_{2},\ldots,x_{m}$, where
each $x_{i}\in\\{1,\ldots,n^{\prime}\\}$, let $c_{i}=|\\{j\mid x_{j}=i\\}|$
denote the number of occurrences of $i$ in the stream $\mathcal{S}^{\prime}$.
Define $F_{\infty}=\max_{1\leq i\leq n^{\prime}}c_{i}$. The following theorem
appears in [38]:

######  Theorem 4.5 ([38]).

For every data stream of length $m$, any randomized streaming algorithm that
computes $F_{\infty}$ to within a $(1\pm 0.2)$ factor with probability at
least $2/3$ requires space $\Omega(\min\\{m,n^{\prime}\\})$.

We remark that, approximating $F_{\infty}$ to within a $(1\pm 0.2)$ factor
means computing a number that is within $(1\pm 0.2)$ factor from $F_{\infty}$;
however, that approximate number may not correspond to the number of
occurrences of a value in the stream.

######  Theorem 4.6.

For every dynamic graph streaming of length $m$ for weighted graphs, any
randomized streaming algorithm that, with probability at least $2/3$,
approximates the maximum-weight $1$-matching of the graph to a $\frac{6}{5}$
factor uses space $\Omega(\\{m,\frac{(n-1)(n-2)}{2}\\})$.

###### Proof.

Given a data stream $\mathcal{S}^{\prime}=x_{1},x_{2},\ldots,x_{m}$, where
each $x_{i}\in\\{1,\ldots,n^{\prime}\\}$, we define a graph stream
$\mathcal{S}$ for a weighted graph $G$ on $n$ vertices, where $n$ satisfies
$(n-1)(n-2)/2<n^{\prime}\leq n(n-1)/2$. Let $V=\\{0\ldots,n-1\\}$ be the
vertex-set of $G$. We first define a bijective function $\chi:\\{(i,j)\mid
i<j\in[n]^{-}\\}\longrightarrow[\frac{n(n-1)}{2}]$. Let $\chi^{-1}$ be the
inverse function of $\chi$. Then, we can translate $\mathcal{S}^{\prime}$ to a
general dynamic graph streaming $\mathcal{S}$ of underlying weighted graph $G$
by corresponding with $x_{i}$ the $i$-th element $(\chi^{-1}(x_{i}),1)$ of
$\mathcal{S}$, for $i\in[m]$. Observe that computing $F_{\infty}$ of
$\mathcal{S}^{\prime}$ is equivalent to computing a maximum-weight 1-matching
for the graph stream $\mathcal{S}$ of $G$. Let $uv$ be a maximum-weight
1-matching of $\mathcal{S}$, then $\chi(uv)$ is $F_{\infty}$ of
$\mathcal{S}^{\prime}$. By Theorem 4.5, it follows that any randomized
approximation streaming algorithm that approximates the maximum-weight
$1$-matching of $G$ to a $\frac{6}{5}$-factor with probability at least $2/3$
uses space $\Omega(\\{m,\frac{(n-1)(n-2)}{2}\\})$, thus completing the proof.
∎

##  5 Insert-Only Streaming Model

In this section, we give a streaming algorithm for p-WT-Matching, and hence
for p-Matching as a special case, in the insert-only model. We start by
defining some notations.

Given a weighted graph $G=(V=\\{0,\ldots,n-1\\},E)$ along with the weight
function $wt:E(G)\longrightarrow\mathbb{R}_{\geq 0}$, and a parameter $k$, we
define a new function $\beta:E(G)\longrightarrow\mathbb{R}_{\geq
0}\times[n]^{-}\times[n]^{-}$ as follows: for $e=uv\in E$, where $u<v$, let
$\beta(e)=(wt(e),u,v)$. Observe that $\beta$ is injective.

Define a partial order relation $\prec$ on $E(G)$ as follows: for any two
distinct edges $e,e^{\prime}\in E(G)$, $e\prec e^{\prime}$ if $\beta(e)$ is
lexicographically smaller than $\beta(e^{\prime})$. For a vertex $v\in V$ and
an edge $e$ incident to $v$, define $\Gamma_{v}$ to be the sequence of edges
incident to $v$, sorted in a decreasing order w.r.t. $\prec$. We say that $e$
is the _$i$ -heaviest_ edge w.r.t. $v$ if $e$ is the $i$-th element in
$\Gamma_{v}$.

Let $f:V\longrightarrow[4k^{2}]^{-}$ be a hash function. Let $H$ be a subgraph
of $G$ (possibly $G$ itself). The function $f$ partitions $V(H)$ into the set
of subsets ${\cal V}=\\{V_{1},\ldots,V_{r}\\}$, where each $V_{i}$, $i\in[r]$,
consists of the vertices in $V(H)$ that have the same image under $f$. A
matching $M$ in $H$ is said to be _nice_ w.r.t. $f$ if no two vertices of $M$
belong to the same part $V_{i}$, where $i\in[r]$, in ${\cal V}$. If $f$ is
clear from the context, we will simply write $M$ is nice. We define the
_compact_ subgraph of $H$ under $f$, denoted ${\mathcal{C}ompact}(H,f)$, as
the subgraph of $H$ consisting of each edge $uv$ in $H$ whose endpoints belong
to different parts, say $u\in V_{i}$, $v\in V_{j}$, $i\neq j\in[r]$, and such
that $\beta(uv)$ is maximum over all edges between $V_{i}$ and $V_{j}$; that
is, $\beta(uv)=\max{\\{\beta(u^{\prime}v^{\prime})\mid u^{\prime}v^{\prime}\in
E(H)\wedge u^{\prime}\in V_{i}\wedge v^{\prime}\in V_{j}\\}}$. Finally, we
define the _reduced compact_ subgraph of $H$ under $f$, denoted
${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$, by (1) selecting each edge
$uv\in{\mathcal{C}ompact}(H,f)$ such that $uv$ is among the $8k$ heaviest
edges (or all edges if there are not that many edges) incident to vertices in
$V_{i}$ and among the $8k$ heaviest edges incident to vertices in $V_{j}$; and
then (2) letting $q=k(16k-1)$ and retaining from the selected edges in (1) the
$q$ heaviest edges (or all edges if there are not that many edges). We have
the following:

######  Lemma 5.1.

The subgraph ${\mathcal{C}ompact}(H,f)$ has a nice $k$-matching if and only if
${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$ has a nice $k$-matching. Moreover, if
${\mathcal{C}ompact}(H,f)$ (and hence
${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$) has a nice $k$-matching, then the
weight of a maximum-weight nice $k$-matching in ${\mathcal{C}ompact}(H,f)$ is
equal to that in ${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$.

###### Proof.

As discussed before, the function $f$ partitions $V(H)$ into the set
$\mathcal{V}=\\{V_{1},\ldots,V_{r}\\}$, where each $V_{i}$, $i\in[r]$,
consists of the vertices in $V(H)$ that have the same image under $f$. Define
the auxiliary weighted graph $\Phi$ whose vertices are the parts
$V_{1},\ldots,V_{r}$, and such that there is an edge $V_{i}V_{j}$ in $\Phi$,
$i\neq j\in[r]$, if some vertex $u\in V_{i}$ is adjacent to some vertex $v\in
V_{j}$ in ${\mathcal{C}ompact}(H,f)$; we associate with edge $V_{i}V_{j}$ the
value $\beta(uv)$ and associate the edge $uv$ with $V_{i}V_{j}$. Obviously,
there is one-to-one correspondence between the nice $k$-matchings in
${\mathcal{C}ompact}(H,f)$ and the $k$-matchings of $\Phi$. Let $\mathscr{H}$
be the subgraph of $\Phi$ formed by selecting each edge $V_{i}V_{j}$, $i\neq
j\in[r]$, such that $V_{i}V_{j}$ is among the $8k$ heaviest edges (or all
edges if there are not that many edges) incident to $V_{i}$ and among the $8k$
heaviest edges (or all edges if there are not that many edges) incident to
$V_{j}$. Let $\mathscr{H^{\prime}}$ consist of the $q$ heaviest edges in
$\mathscr{H}$; if $\mathscr{H}$ has at most $q$ edges, we let ${\cal
H^{\prime}}={\cal H}$. Since there is a one-to-one correspondence between the
nice $k$-matchings in ${\mathcal{C}ompact}(H,f)$ and the $k$-matchings of
$\Phi$, it suffices to prove the statement of the lemma with respect to
matchings in $\Phi$ and ${\cal H^{\prime}}$; namely, since ${\cal H^{\prime}}$
is a subgraph of $\Phi$, it suffices to show that: if $\Phi$ has a maximum-
weight $k$-matching $M$ then ${\cal H^{\prime}}$ has a maximum-weight
$k$-matching of the same weight as $M$.

Suppose that $\Phi$ has a maximum-weight $k$-matching $M$. Choose $M$ such
that the number of edges in $M$ that remain in ${\cal H}$ is maximized. We
will show first that all the edges in $M$ remain in ${\cal H}$. Suppose not,
then there is an edge $V_{i_{0}}V_{i_{1}}\in M$ such that $V_{i_{0}}V_{i_{1}}$
is not among the $8k$ heaviest edges incident to one of its endpoints, say
$V_{i_{1}}$. Since $|V(M)|=2k<8k$, it follows that there is a heaviest edge
$V_{i_{1}}V_{i_{2}}$ incident to $V_{i_{1}}$ such that
$\beta(V_{i_{1}}V_{i_{2}})>\beta(V_{i_{0}}V_{i_{1}})$ and $V_{i_{2}}\notin
V_{M}$. If $V_{i_{1}}V_{i_{2}}\in\mathscr{H}$, then
$(M-V_{i_{0}}V_{i_{1}})+V_{i_{1}}V_{i_{2}}$ is a maximum-weight $k$-matching
of $\Phi$ that contains more edges of $\mathscr{H}$ than $M$, contradicting
our choice of $M$. It follows that $V_{i_{1}}V_{i_{2}}\notin\mathscr{H}$.
Then, $V_{i_{1}}V_{i_{2}}$ is not among the $8k$ heaviest edges incident to
$V_{i_{2}}$. Now apply the above argument to $V_{i_{2}}$ to select the
heaviest edge $V_{i_{2}}V_{i_{3}}$ such that
$\beta(V_{i_{2}}V_{i_{3}})>\beta(V_{i_{1}}V_{i_{2}})>\beta(V_{i_{0}}V_{i_{1}})$
and $V_{i_{3}}\notin V_{M}$. By applying the above argument $j$ times, we
obtain a sequence of $j$ vertices $V_{i_{1}},V_{i_{2}},\ldots,V_{i_{j}}$, such
that (1) $\\{V_{i_{2}},\ldots,V_{i_{j}}\\}\cap V_{M}=\emptyset$; and (2)
$V_{i_{a}}\neq V_{i_{b}}$ for every $a\neq b\in[j]$, which is guaranteed by
$\beta(V_{i_{a}}V_{i_{a+1}})<\beta(V_{i_{a+1}}V_{i_{a+2}})<\cdots<\beta(V_{i_{b-1}}V_{i_{b}})$
and $V_{i_{a}}V_{i_{a+1}}$ is the heaviest edge incident to $V_{i_{a}}$ such
that $V_{i_{a+1}}\notin V_{M}$. Since $\Phi$ is finite, the above process must
end at an edge $e$ not in $M$ and such that $\beta(e)$ exceeds
$\beta(V_{i_{0}}V_{i_{1}})$, contradicting our choice of $M$. Therefore,
$M\subseteq E({\cal H})$.

Now, choose a maximum-weight $k$-matching of ${\cal H}$ that maximizes the
number of edges retained in ${\cal H^{\prime}}$. Without loss of generality,
call it $M$. We prove that the edges of $M$ are retained in ${\cal
H^{\prime}}$, thus proving the lemma. Suppose that this is not the case. Since
each vertex in $V(M)$ has degree at most $8k$ and one of its edges must be in
$M$, the number of edges in ${\cal H}$ incident to the vertices in $M$ is at
most $2k(8k-1)+k=k(16k-1)=q$. It follows that there is an edge $e$ in ${\cal
H^{\prime}}$ whose endpoints are not in $M$ and such that $\beta(e)$ is larger
than the $\beta()$ value of some edge in $M$, contradicting our choice of $M$.
∎

######  Lemma 5.2.

Let $f:V\longrightarrow[4k^{2}]^{-}$ be a hash function, and let $H$ be a
subgraph of $G$. There is an algorithm Alg-Reduce($H$, $f$) that computes
${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$ and whose time and space complexity
is $\mathcal{O}(|H|+k^{2})$.

###### Proof.

The algorithm Alg-Reduce($H$, $f$) works as follows. First, for each $v\in
V(H)$, it computes $f(v)$ and uses it to partition $V(H)$ into
$V_{1},\ldots,V_{r}$, where each $V_{i}$, $i\in[r]$, consists of the vertices
in $V(H)$ that have the same image under $f$. Clearly, the above can be done
in time $\mathcal{O}(|H|+k^{2})$ (e.g., using Radix sort). Then, it partitions
the edges of $H$ into groups $E_{i,j}$, $i\neq j\in[r]$, where each $E_{i,j}$
consists of all the edges in $H$ that go between $V_{i}$ and $V_{j}$. Clearly,
this can be done in $\mathcal{O}(|H|)$ time (e.g., using Radix sort on the
labels of the pairs of parts containing the edges). From each group $E_{i,j}$,
among all edge in $E_{i,j}$, the algorithm retains the edge $uv$ corresponding
to the maximum value $\beta(uv)$, which clearly can be done in
$\mathcal{O}(|H|)$ time. Next, the algorithm groups the remaining edges into
(overlapping) groups, where each group $E_{i}$ consists of all the edges
(among the remaining edges) that are incident to the same part $V_{i}$, for
$i\in[r]$; note that each edge appears in exactly two such groups. The
algorithm now discards every edge $uv$, where $u\in V_{i}$, $v\in V_{j}$, if
either $uv$ is not among the heaviest $8k$ edges in $E_{i}$ or is not among
the $8k$ heaviest edges in $E_{j}$. The above can be implemented in
$\mathcal{O}(|H|)$ time by applying a linear-time ($(8k)$-th order) selection
algorithm [11] to each $E_{i}$ to select the $(8k)$-th heaviest edge in
$E_{i}$, and then discard all edges of lighter weight from $E_{i}$; an edge is
kept if it is kept in both groups that contain its endpoints (which can be
easily done, e.g., using a Radix sort). Finally, invoking a $q$-th order
selection algorithm [11], where $q=k(16k-1)$, we can retain the heaviest $q$
edges among the remaining edges; those edges form
${\mathcal{R}ed}$-${\mathcal{C}om}(H,f)$. The above algorithm runs in time
$\mathcal{O}(|H|+k^{2})$, and its space complexity is dominated by
$\mathcal{O}(|H|+k^{2})$ as well. This completes the proof. ∎

We now present the streaming algorithm $\mathcal{A}_{Insert}$ for p-WT-
Matching. Let $(\mathcal{S},k)$ be an instance of p-WT-Matching, where
$\mathcal{S}=(e_{1},wt(e_{1})),\ldots,(e_{i},wt(e_{i})),\ldots$ is a stream of
edge-insertions for a graph $G$. For $i\in\mathbb{N}$, let $G_{i}$ be the
subgraph of $G$ consisting of the first $i$ edges $e_{1},\ldots,e_{i}$ of
$\mathcal{S}$, and for $j\leq i$, let $G_{j,i}$ be the subgraph of $G$ whose
edges are $\\{e_{j},\ldots,e_{i}\\}$; if $j>i$, we let $G_{j,i}=\emptyset$.
Let $f$ be a hash function chosen u.a.r. from a universal set $\mathcal{H}$ of
hash functions mapping $V$ to $[4k^{2}]^{-}$. The algorithm
$\mathcal{A}_{Insert}$, after processing the $i$-th element
$(e_{i},wt(e_{i}))$, computes two subgraphs $G_{i}^{f},G_{i}^{s}$ defined as
follows. For $i=0$, define $G_{i}^{f}=G_{i}^{s}=\emptyset$. Suppose now that
$i>0$. Define $\hat{i}$ to be the largest multiple of $q$ that is smaller than
$i$, that is, $i=\hat{i}+p$, where $0<p\leq q$; and define $i^{*}$ as the
largest multiple of $q$ that is smaller than $\hat{i}$ if $\hat{i}>0$, and $0$
otherwise (i.e., $i^{*}=0$ if $\hat{i}=0$). The subgraph $G_{i}^{f}$ is
defined only when $i$ is a multiple of $q$ (i.e., $i=j\cdot q$ where $j\geq
0$), and is defined recursively for $i=j\cdot q>0$ as
$G_{i}^{f}={\mathcal{R}ed}$-${\mathcal{C}om}(G_{\hat{i}}^{f}\cup
G_{i^{*}+1,\hat{i}})$; that is, $G_{i}^{f}$ is the reduced compact subgraph of
the graph consisting of $G_{\hat{i}}^{f}$ plus the subgraph consisting of the
edges encountered after $e_{i^{*}}$, starting from $e_{i^{*}+1}$ up to
$e_{\hat{i}}$. The subgraph $G_{i}^{s}$ is defined as
$G_{i}^{s}=G_{\hat{i}}^{f}\cup G_{i^{*}+1,i}$; that is, $G_{i}^{s}$ consists
of the previous (before $i$) reduced compact subgraph plus the subgraph
consisting of the edges starting after $i^{*}$ up to $i$. We refer to Figure 2
for an illustration of the definitions of $G_{i}^{f}$ and $G_{i}^{s}$.

######  Observation 5.3.

For each $i$ that is a multiple of $q$, $G_{i}^{f}$ contains at most $q$ edges
(by the definition of a reduced compact subgraph).

######  Observation 5.4.

For each $i$, $G_{i}^{s}$ contains at most $3q$ edges.

######  Lemma 5.5.

For each $i\geq 1$, if $G_{i}$ contains a maximum-weight $k$-matching, then
with probability at least $1/2$, $G_{i}^{s}$ contains a maximum-weight
$k$-matching of $G_{i}$.

###### Proof.

Let $M=\\{u_{0}u_{1},\ldots,u_{2k-2}u_{2k-1}\\}$ be a maximum-weight
$k$-matching in $G_{i}$, and let $V_{M}=\\{u_{0},\ldots,u_{2k-1}\\}$. Since
$f$ is a hash function chosen u.a.r. from a universal set $\mathcal{H}$ of
hash functions mapping $V$ to $[4k^{2}]^{-}$, by Theorem 2.3, with probability
at least $1/2$, $f$ is perfect w.r.t. $V_{M}$. Now, suppose that $f$ is
perfect w.r.t. $V_{M}$, and hence, we have $f(u_{j})\neq f(u_{l})$ for every
$j\neq l\in[2k]^{-}$. Thus, $M$ is a nice matching (w.r.t. $f$) in $G_{i}$. By
the definition of ${\mathcal{C}ompact}(G_{i},f)$, there is a set $M^{\prime}$
of $k$ edges
$M^{\prime}=\\{u^{\prime}_{0}u^{\prime}_{1},\ldots,u^{\prime}_{2k-2}u^{\prime}_{2k-1}\\}$
in ${\mathcal{C}ompact}(G_{i},f)$ such that
$\\{f(u^{\prime}_{2i}),f(u^{\prime}_{2i+1})\\}=\\{f(u_{2i}),f(u_{2i+1})\\}$
and $\beta(u^{\prime}_{2i}u^{\prime}_{2i+1})\geq\beta(u_{2i}u_{2i+1})$ for
$i\in[k]^{-}$. It follows that $wt(u^{\prime}_{2i}u^{\prime}_{2i+1})\geq
wt(u_{2i}u_{2i+1})$ for $i\in[k]^{-}$. Therefore,
${\mathcal{C}ompact}(G_{i},f)$ contains a maximum-weight $k$-matching of
$G_{i}$, namely
$\\{u^{\prime}_{0}u^{\prime}_{1},\ldots,u^{\prime}_{2k-2}u^{\prime}_{2k-1}\\}$;
moreover, this matching is nice. By Lemma 5.1,
${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i},f)$ contains a maximum-weight
$k$-matching of ${\mathcal{C}ompact}(G_{i},f)$.

Next, we prove that $G_{i}^{s}$ contains a maximum-weight $k$-matching of
$G_{i}$. If $i\leq 2q$, then $G_{i}^{s}=G_{1,i}=G_{i}$ by definition, and
hence $G_{i}^{s}$ contains a maximum-weight $k$-matching of $G_{i}$. Suppose
now that $i>2q$. By definition, $G_{i}^{s}=G_{\hat{i}}^{f}\cup G_{i^{*}+1,i}$.
(Recall that, by definition, $G_{q}^{f}$=$\emptyset$,
$G_{2q}^{f}={\mathcal{R}ed}$-${\mathcal{C}om}(G_{q}^{f}\cup G_{1,q})$,
$G_{3q}^{f}={\mathcal{R}ed}$-${\mathcal{C}om}(G_{2q}^{f}\cup
G_{q+1,2q}),\ldots,$
$G_{\hat{i}}^{f}={\mathcal{R}ed}$-${\mathcal{C}om}(G_{i^{*}}^{f}\cup
G_{i^{*}-q+1,i^{*}})$.) For each $j\geq 1$ that is multiple of $q$, let
$\mathscr{G}_{j}$ be the graph consisting of the edges that are in
$G_{\hat{j}}^{f}\cup G_{j^{*}+1,\hat{j}}$ but are not kept in $G_{j}^{f}$.
Consequently, $(\bigcup_{q\leq j<\hat{i},j\text{ is a multiple of
}q}\mathscr{G}_{j})\bigcup G_{\hat{i}}^{f}=G_{i^{*}}$. By the definition of
${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i},f)$, it is easy to verify that
${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i},f)$ does not contain the edges in
$\mathscr{G}_{j}$, for each $j\geq 1$. It follows that
${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i},f)$ is a subgraph of $G_{i}^{s}$, and
hence, $G_{i}^{s}$ contains a maximum-weight $k$-matching of
${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i},f)$, and hence of
${\mathcal{C}ompact}(G_{i},f)$ by the above discussion. Since
${\mathcal{C}ompact}(G_{i},f)$ contains a maximum-weight $k$-matching of
$G_{i}$, $G_{i}^{s}$ contains a maximum-weight $k$-matching of $G_{i}$. It
follows that, with probability at least $1/2$, $G_{i}^{s}$ contains a maximum-
weight $k$-matching of $G_{i}$. ∎

. . . .
.$e_{1}$$e_{q}$$e_{2q}$$e_{i^{*}}$$e_{i^{*}+1}$$e_{\hat{i}}$$e_{i}$$q$$2q$$i^{*}$$i^{*}$$\hat{i}$$i=jq$${\mathcal{R}ed}$-${\mathcal{C}om}(G_{i^{*}+1,\hat{i}}\cup
G_{\hat{i}}^{f})$$=G_{i}^{f}$

(a) The definition of $G_{i}^{f}$

. . . .
.$e_{1}$$e_{q}$$e_{2q}$$e_{i^{*}}$$e_{i^{*}+1}$$e_{\hat{i}}$$e_{i}$$q$$2q$$i^{*}$$i^{*}$$\hat{i}$$i\neq
jq$$G_{i^{*}+1,i}\cup G_{\hat{i}}^{f}=G_{i}^{s}$

(b) The definition of $G_{i}^{s}$.

Figure 2: Illustration of the definitions of $G_{i}^{f}$ and $G_{i}^{s}$.

The algorithm ${\cal A}_{Insert}$, when queried at the end of the stream,
either returns a maximum-weight $k$-matching of $G$ or the empty set. To do
so, at every instant $i$, it will maintain a subgraph $G_{i}^{s}$ that will
contain the edges of the desired matching, from which this matching can be
extracted. To maintain $G_{i}^{s}$, the algorithm keeps track of the subgraphs
$G_{i-1}^{s}$, $G_{\hat{i}}^{f}$, the edges $e_{i^{*}+1},\ldots,e_{i}$, and
will use them in the computation of the subgraph $G_{i}^{s}$ as follows. If
$i$ is not a multiple of $q$, then $G_{i}^{s}=G_{i-1}^{s}+e_{i}$, and the
algorithm simply computes $G_{i}^{s}$ as such. Otherwise (i.e., $i$ is a
multiple of $q$), $G_{i}^{s}=G_{\hat{i}}^{f}\cup G_{i^{*}+1,i}$, and the
algorithm uses $G_{\hat{i}}^{f}$ and
$G_{i^{*}+1,i}=\\{e_{i^{*}+1},\ldots,e_{i}\\}$ to compute and return
$G_{i}^{s}$; however, in this case (i.e., $i$ is a multiple of $q$), the
algorithm will additionally need to have $G_{i}^{f}$ already computed, in
preparation for the potential computations of subsequent $G_{j}^{s}$, for
$j\geq i$. By Lemma 5.2, the subgraph $G_{i}^{f}$ can be computed by invoking
the Alg-Reduce in Lemma 5.2 on $G_{\hat{i}}^{f}\cup G_{i^{*}+1,\hat{i}}$,
which runs in time $\mathcal{O}(q)$. Note that both $G_{\hat{i}}^{f}$ and
$G_{i^{*}+1,\hat{i}}$ are available to ${\cal A^{\prime}}$ at each of the
steps $\hat{i}+1,\ldots,i$. Therefore, the algorithm will stagger the
$\mathcal{O}(q)$ many operations needed for the computation of $G_{i}^{f}$
uniformly (roughly equally) over each of the steps $\hat{i}+1,\ldots,i$,
yielding an $\mathcal{O}(1)$ operations per step. Note that all the operations
in Alg-Reduce can be explicitly listed, and hence, splitting them over an
interval of $q$ steps is easily achievable. Suppose that Alg-Reduce is split
into $q$ operations $\Lambda_{1},\ldots,\Lambda_{q}$ such that each operation
takes time $\mathcal{O}(1)$. The algorithm $\cal A^{\prime}$ is given in
Figure 4:

Algorithm 4 The streaming algorithm $\mathcal{A}_{Insert}$ in the insert-only
streaming model

1:

2:$\mathcal{A}_{Insert}$-Preprocessing: The preprocessing algorithm

3:

4:$n=|V(G)|$ and a parameter $k\in\mathbb{N}$

5:let $f\in_{u.a.r.}\mathcal{H}$, where $\mathcal{H}$ is a set of universal
hash functions from $V$ to $[4k^{2}]^{-}$

6:

7:$\mathcal{A}_{Insert}$-Update: The update algorithm

8:

9:The $i$-th element $(e_{i}=uv,wt(e))\in\mathcal{S}$

1:let $j=i\mod q$

2:if $j$ is $0$ then

3: execute $\Lambda_{q}$

4: $G_{i}^{s}=G_{\hat{i}}^{f}\cup G_{i^{*}+1,i}$

5:else

6: execute $\Lambda_{j}$

7: $G_{i}^{s}=G_{i-1}^{s}\cup e_{i}$

8:

9:$\mathcal{A}_{Insert}$-Query: An algorithm to answer query after the $i$-th
update

10:

1:return a maximum-weight $k$-matching in $G_{i}^{s}$ if any; otherwise,
return $\emptyset$

######  Lemma 5.6.

The algorithm $\mathcal{A}_{Insert}$ runs in space $\mathcal{O}(k^{2})$ and
has update time $\mathcal{O}(1)$.

###### Proof.

$\mathcal{A}_{Insert}$-Preprocessing takes $\mathcal{O}(1)$ space to store
$f$. The space needed for $\mathcal{A}_{Insert}$-Update is dominated by that
needed for storing $G_{i}^{s},G_{i}^{f}$, $G_{i^{*}+1,i},G_{i^{*}+1,\hat{i}}$,
and the space needed to execute Alg-Reduce. By the definition of the subgraphs
$G_{i}^{s}$, $G_{i}^{f}$, $G_{i^{*}+1,i}$, $G_{i^{*}+1,\hat{i}}$, each has
size $\mathcal{O}(q)$, and hence can be stored using
$\mathcal{O}(q)=\mathcal{O}(k^{2})$ space. By Lemma 5.2, Alg-Reduce runs in
space $\mathcal{O}(k^{2})$. Hence, the overall space complexity of ${\cal
A^{\prime}}$ is $\mathcal{O}(k^{2})$. $\mathcal{A}_{Insert}$-Query takes space
$\mathcal{O}(q)=\mathcal{O}(k^{2})$ [19, 20], since $G_{i}^{s}$ contains at
most $\mathcal{O}(q)$ edges. Altogether, $\mathcal{A}_{Insert}$ runs in space
$\mathcal{O}(k^{2})$.

For the update time, as discussed above, we can take the operations performed
by Algorithm Alg-Reduce to compute $G_{i}^{f}$, during any interval of $q$
steps, and stagger them uniformly over the $q$ steps of the interval. Since
Alg-Reduce performs $\mathcal{O}(q)$ many operations to compute $G_{i}^{f}$ by
Lemma 5.2, this yields an $\mathcal{O}(1)$ operations per step. It follows
that the update time of $\mathcal{A}_{Insert}$ is $\mathcal{O}(1)$, thus
completing the proof. ∎

Without loss of generality, and for convenience, we will assume that the
algorithm is queried at the end of the stream $\mathcal{S}$, even though the
query could take place after any arbitrary operation $i$.

######  Theorem 5.7.

Let $0<\delta<1$ be a parameter. In the insert-only streaming model, there is
an algorithm for p-WT-Matching such that, on input $(\mathcal{S},k)$, the
algorithm outputs a matching $M^{\prime}$ satisfying that (1) if $G$ contains
a $k$-matching then, with probability at least $1-\delta$, $M^{\prime}$ is a
maximum-weight $k$-matching of $G$; and (2) if $G$ does not contain a
$k$-matching then $M^{\prime}=\emptyset$. The algorithm runs in
$\mathcal{O}(k^{2}\log\frac{1}{\delta})$ space and has
$\mathcal{O}(\log\frac{1}{\delta})$ update time. In particular, for any
constant $\delta$, the algorithm runs in space $\mathcal{O}(k^{2})$ and has
$\mathcal{O}(1)$ update time.

###### Proof.

Run $\lceil\log\frac{1}{\delta}\rceil$-many copies of algorithm
$\mathcal{A}_{Insert}$ in parallel (i.e., using dove-tailing). Then, by the
end of the stream, there are $\lceil\log\frac{1}{\delta}\rceil$ copies of
$G_{m}^{s}$, where $m$ is the length of the stream. Let $G^{\prime}$ be the
union of all the $G_{m}^{s}$’s produced by the runs of $\mathcal{A}_{Insert}$.
If $G^{\prime}$ has a $k$-matching, let $M^{\prime}$ be a maximum-weight
$k$-matching of $G^{\prime}$; otherwise, let $M^{\prime}=\emptyset$.

By Lemma 5.5, if $G_{m}$, i.e., $G$, contains a maximum-weight $k$-matching,
with probability at least $1/2$, one copy of $G_{m}^{s}$ contains a maximum-
weight $k$-matching of $G$. Hence, with probability at least
$1-(1/2)^{\lceil\log\frac{1}{\delta}\rceil}\geq 1-\delta$, $G^{\prime}$
contains a maximum-weight $k$-matching of $G$. It follows that if $G$ contains
a maximum-weight $k$-matching $M$ then, with probability at least $1-\delta$,
$G^{\prime}$ contains a maximum-weight $k$-matching of the same weight as $M$
and hence $M^{\prime}$ is a maximum-weight $k$-matching of $G$.

Observe that the graph $G^{\prime}$ is a subgraph of $G$. Therefore, statement
(2) in the theorem clearly holds true.

By Lemma 5.6, the above algorithm runs in space
$\mathcal{O}(k^{2}\log\frac{1}{\delta})$ and has update time
$\mathcal{O}(\log\frac{1}{\delta})$, thus completing the proof. ∎

##  6 Concluding Remarks

In this paper, we presented streaming algorithms for the $k$-matching problem
in both the dynamic and insert-only streaming models. Our results improve
previous works and achieve optimal space and update-time complexity. Our
result for the weighted $k$-matching problem was achieved using a newly-
developed structural result that is of independent interest.

An obvious open question that ensues from our work is whether the dependency
on the number of distinct weights $W$ in our result, and the result in [8] as
well, for weighted $k$-matching in the dynamic streaming model can be lifted.
More specifically, does there exist a dynamic streaming algorithm for p-WT-
Matching whose space complexity is $\tilde{O}(k^{2})$ and update time is
$\tilde{O}(1)$? We leave this as an (important) open question for future
research.

## References

  * [1] Kook Jin Ahn and Sudipto Guha.  Linear programming in the semi-streaming model with application to the maximum matching problem.  Information and Computation, 222:59–79, 2013.
  * [2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: sparsification, spanners, and subgraphs.  In Proceedings of the 31st ACM Symposium on Principles of Database Systems (PODS ’12), pages 5–14, 2012.
  * [3] KookJin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth.  Correlation clustering in data streams.  In Proceedings of the 32nd International Conference on Machine Learning (ICML ’15), pages 2237–2246, 2015.
  * [4] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  Journal of Computer and System Sciences, 58(1):137 – 147, 1999\.
  * [5] Sepehr Assadi, Sanjeev Khanna, and Yang Li.  On estimating maximum matching size in graph streams.  In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’17), pages 1723–1742, 2017.
  * [6] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.  Maximum matchings in dynamic graph streams and the simultaneous communication model.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’16), pages 1345–1364, 2016.
  * [7] Jianer Chen, Ying Guo, and Qin Huang.  Linear-time parameterized algorithms with limited local resources.  arXiv preprint arXiv:2003.02866, 2020.
  * [8] 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 Proceedings of the 27th annual ACM-SIAM symposium on Discrete algorithms (SODA ’16), pages 1326–1344, 2016.
  * [9] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh.  New streaming algorithms for parameterized maximal matching and beyond.  In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’15), pages 56–58, 2015.
  * [10] Rajesh Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh.  Parameterized streaming: Maximal matching and vertex cover.  In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’15), pages 1234–1251, 2015.
  * [11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [12] Graham Cormode and Donatella Firmani.  A unifying framework for $\ell_{0}$-sampling algorithms.  Distributed and Parallel Databases, 32(3):315–335, 2014.
  * [13] Michael Crouch and Daniel S. Stubbs.  Improved streaming algorithms for weighted matching, via unweighted matching.  In Proceedings of APPROX/RANDOM ’14, volume 28, pages 96–104, 2014.
  * [14] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [15] Leah Epstein, Asaf Levin, Julián 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.
  * [16] Stefan Fafianie and Stefan Kratsch.  Streaming kernelization.  In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science 2014 (MFCS ’14), pages 275–286, 2014.
  * [17] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theoretical Computer Science, 348(2-3):207–216, 2005.
  * [18] Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, and Mahesh Viswanathan.  An approximate l1-difference algorithm for massive data streams.  SIAM Journal on Computing, 32(1):131–151, January 2003.
  * [19] Harold N. Gabow.  Data structures for weighted matching and nearest common ancestors with linking.  In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’90), page 434–443. SIAM, 1990.
  * [20] Harold N. Gabow.  Data structures for weighted matching and extensions to b-matching and f-factors.  ACM Transactions on Algorithms, 14(3), 2018.
  * [21] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  On the communication and streaming complexity of maximum bipartite matching.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), pages 468–485, 2012.
  * [22] Ashish Goel, Michael Kapralov, and Ian Post.  Single pass sparsification in the streaming model with edge deletions.  arXiv preprint arXiv:1203.4900, 2012.
  * [23] Piotr Indyk.  Stable distributions, pseudorandom generators, embeddings, and data stream computation.  Journal of the ACM, 53(3):307–323, May 2006.
  * [24] Hossein Jowhari, Mert Sağlam, and Gábor Tardos.  Tight bounds for lp samplers, finding duplicates in streams, and related problems.  In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS ’11), page 49–58, 2011.
  * [25] Michael Kapralov.  Better bounds for matchings in the streaming model.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’13), pages 1679–1697, 2013.
  * [26] Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.  Approximating matching size from random streams.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’14), pages 734–751, 2014.
  * [27] Michael Kapralov and David Woodruff.  Spanners and sparsifiers in dynamic streams.  In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC ’14), pages 272–281, 2014.
  * [28] Christian Konrad, Frédéric Magniez, and Claire Mathieu.  Maximum matching in semi-streaming with few passes.  In Proceedings of APPROX/RANDOM ’12, pages 231–242, 2012.
  * [29] Christian Konrad and Adi Rosén.  Approximating semi-matchings in streaming and in two-party communication.  In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP ’13), pages 637–649, 2013.
  * [30] Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche.  Data reduction for maximum matching on real-world graphs: Theory and experiments.  In 26th Annual European Symposium on Algorithms (ESA ’18), volume 112 of LIPIcs, pages 53:1–53:13, 2018.
  * [31] Roie Levin and David Wajc.  Streaming submodular matching meets the primal-dual method.  arXiv preprint arXiv:2008.10062, to appear in SODA ’21, 2020\.
  * [32] Andrew McGregor.  Finding graph matchings in data streams.  In Proceedings of APPROX/RANDOM ’05, pages 170–181, 2005.
  * [33] Andrew McGregor.  Graph stream algorithms: A survey.  SIGMOD Record, 43(1):9–20, May 2014.
  * [34] George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche.  Computing maximum matchings in temporal graphs.  In 37th International Symposium on Theoretical Aspects of Computer Science (STACS ’20), volume 154 of LIPIcs, pages 27:1–27:14, 2020\.
  * [35] George B. Mertzios, André Nichterlein, and Rolf Niedermeier.  A linear-time algorithm for maximum-cardinality matching on cocomparability graphs.  SIAM Journal on Discrete Mathematics, 32(4):2820–2835, 2018.
  * [36] George B. Mertzios, André Nichterlein, and Rolf Niedermeier.  The power of linear-time data reduction for maximum matching.  Algorithmica, 82(12):3521–3565, 2020.
  * [37] Ami Paz and Gregory Schwartzman.  A (2+$\epsilon$)-approximation for maximum weight matching in the semi-streaming model.  ACM Transaction on Algorithms, 15(2):18:1–18:15, 2019.
  * [38] Tim Roughgarden.  Communication complexity (for algorithm designers).  arXiv preprint arXiv:1509.06257, 2015.
  * [39] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan.  Chernoff-hoeffding bounds for applications with limited independence.  SIAM Journal on Discrete Mathematics, 8(2):223–250, 1995.
  * [40] Robert E. Tarjan.  Data structures and network algorithms.  SIAM, 1983.
  * [41] Salil P. Vadhan.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012.
  * [42] Mariano Zelke.  Weighted matching in the semi-streaming model.  Algorithmica, 62(1-2):1–20, 2012.