# Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on
Sparse Graphs

Xiuge Chen
<EMAIL_ADDRESS>School of Computing and Information Systems, The
University of Melbourne, AU. Rajesh Chitnis
<EMAIL_ADDRESS>School of Computer Science, University of Birmingham,
UK. Patrick Eades11footnotemark: 1
<EMAIL_ADDRESS>Anthony Wirth11footnotemark: 1
<EMAIL_ADDRESS>
###### Abstract

In this paper, we design sub-linear space streaming algorithms for estimating
three fundamental parameters – maximum independent set, minimum dominating set
and maximum matching – on sparse graph classes, i.e., graphs which satisfy
$m=O(n)$ where $m,n$ is the number of edges, vertices respectively. Each of
the three graph parameters we consider can have size $\Omega(n)$ even on
sparse graph classes, and hence for sublinear-space algorithms we are
restricted to parameter estimation instead of attempting to find a solution.
We obtain these results:

  * •

Estimating Max Independent Set via the Caro-Wei bound: Caro and Wei each
showed $\lambda=\sum_{v}{1}/(d(v)+1)$ is a lower bound on max independent set
size, where vertex $v$ has degree $d(v)$. If average degree, $\bar{d}$, is
$\mathcal{O}(1)$, and max degree
$\Delta=\mathcal{O}({\varepsilon}^{2}\bar{d}^{-3}n)$, our algorithms, with at
least $1-\delta$ success probability:

    * –

In _online streaming_ , return an actual independent set of size
$1\pm{\varepsilon}$ times $\lambda$. This improves on Halldórsson et al.
[Algorithmica ’16]: we have less working space, i.e.,
$\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log n\cdot\log\delta^{-1})$, faster
updates, i.e., $\mathcal{O}(\log{\varepsilon}^{-1})$, and bounded success
probability.

    * –

In _insertion-only_ streams, approximate $\lambda$ within factor
$1\pm{\varepsilon}$, in one pass, in
$\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log n\cdot\log\delta^{-1})$ space. This
aligns with the result of Cormode et al. [ISCO ’18], though our method also
works for _online streaming_. In a vertex-arrival and random-order stream,
space reduces to $\mathcal{O}(\log(\bar{d}{\varepsilon}^{-1}))$. With extra
space and post-processing step, we remove the max-degree constraint.

  * •

Sublinear-Space Algorithms on Forests: On a forest, Esfandiari et al. [SODA
’15, TALG ’18] showed space lower bounds for $1$-pass randomized algorithms
that approximately estimate these graph parameters. We narrow the gap between
upper and lower bounds:

    * –

Max independent set size within $3/2\cdot(1\pm{\varepsilon})$ in one pass and
in $\log^{\mathcal{O}(1)}n$ space, and within $4/3\cdot(1\pm{\varepsilon})$ in
two passes and in $\tilde{\mathcal{O}}(\sqrt{n})$ space; the lower bound is
for approx. $\leq 4/3$.

    * –

Min dominating set size within $3\cdot(1\pm{\varepsilon})$ in one pass and in
$\log^{\mathcal{O}(1)}n$ space, and within $2\cdot(1\pm{\varepsilon})$ in two
passes and in $\tilde{\mathcal{O}}(\sqrt{n})$ space; the lower bound is for
approx. $\leq 3/2$.

    * –

Max matching size within $2\cdot(1\pm{\varepsilon})$ in one pass and in
$\log^{\mathcal{O}(1)}n$ space, and within $3/2\cdot(1\pm{\varepsilon})$ in
two passes and in $\tilde{\mathcal{O}}(\sqrt{n})$ space; the lower bound is
for approx. $\leq 3/2$.

##  1 Introduction

Maximum independent set, minimum dominating set, and maximum matching are key
graph problems. Independent set models, for example, optimization and
scheduling problems where conflicts should be avoided [1, 21, 24, 31],
dominating set models guardian selection problems [36, 38, 42, 43, 47], while
a matching models similarity [14, 20, 45] and inclusion dependencies [3, 16].
When the input is presented as a data stream, we show new algorithms for
computing the following parameters related to these problems on sparse graphs.

Parameters of interest: Given an undirected graph $G$, comprising vertices $V$
and edges $E$, let $n$ and $m$ be the sizes of $V$ and $E$, respectively. A
subset $S$ of $V$ is an _independent set_ if and only if the subgraph induced
by $S$ contains no edges. Subset $S$ is a _dominating set_ if and only if
every vertex in $V$ is either in $S$ or adjacent to some vertex in $S$. A
subset $M$ of $E$ is a _matching_ if and only if no pair of edges in $M$ share
a vertex. The three parameters of interest to us are the size of a maximum
independent set, aka _independence number_ , $\beta$; the size of a minimum
dominating set, aka _domination number_ , $\gamma$; and the size of a maximum
matching, aka _matching number_ , $\phi$. It is well known that
$n-\phi\geq\beta\geq n-2\phi$.

Given some $k$, it is NP-complete [30] to decide whether $\beta\geq k$ and to
decide whether $\gamma\leq k$. There are several _approximation algorithms_
for these problems that run in polynomial time and return a solution within a
guaranteed factor of optimum. For instance, a greedy algorithm for maximum
matching outputs a $2$-approximation. Similarly, there exist greedy algorithms
that $\mathcal{O}(\Delta)$-approximate the maximum independent set [23] and
approximate within $\mathcal{O}(\ln\Delta)$ the minimum dominating set [27,
33], where $\Delta$ is the maximum degree. More promising results are obtained
on sparse graphs, where $m\in\mathcal{O}(n)$, which we study in this paper.
For example, the Caro-Wei bound [7, 46] $\lambda=\sum_{v\in
V(G)}(1+\text{deg}(v))^{-1}$ is a lower bound on $\beta$.

Data streams: We focus on estimating these graph parameters in the data stream
model. The _semi-streaming_ model [19], with $\mathcal{O}(n\log n)$ bits of
working space, is commonplace for general graphs. In this paper we consider
_sparse_ graphs: as $\mathcal{O}(n)$ bits would be sufficient to store the
entire sparse graph, we restrict our space allowance to $o(n)$ bits. We _tune_
our algorithms to specific stream formats: edge-arrival, vertex-arrival,
insertion-only, turnstile, arbitrary, and random. A graph stream is _edge-
arrival_ if edges arrive one by one, sequentially, in arbitrary order. We call
a graph stream _insertion-only_ if there are no deletions. In a _turnstile_
stream, an edge can be deleted, but only if its most recent operation was an
insertion. It is _vertex-arrival_ if it comprises a sequence of
$(\text{vertex},\text{vertex-list})$ pairs, $(u_{i},A_{i})$, where the list
$A_{i}$ comprises the subset of the vertices $\\{u_{j}\\}_{j<i}$ that have
occurred previously in the stream that are adjacent to $u_{i}$. Moreover, the
order of vertex arrivals can be either _arbitrary_ or (uniformly) _random_.

Halldórsson et al. [22] introduced the _online streaming_ model, combining the
data-stream and online models. In _online streaming_ , after each stream item,
on demand, the algorithm must efficiently report a valid solution. Typically,
an online-streaming algorithm has a initial solution and modifies it element
by element. Similar to the _online_ model, each decision on the solution is
irrevocable. We distinguish between _working space_ , involved in computing
the solution, and an additional _solution space_ for storing or returning the
solution. Solution space may be significantly larger than the working space,
but is write only.

###  1.1 Previous Results

To further set the scene for our contributions, we describe some of the
streaming-algorithm context. On graphs with bounded arboricity, $\alpha$,
there are known approximation algorithms for estimating the matching number,
$\phi$. For insertion-only streams, Esfandiari et al. [18] developed a
$(5\alpha+9)$-approximation algorithm that requires
$\tilde{\mathcal{O}}(\alpha n^{2/3})$ space. Cormode et al. [12] traded off
approximation ratio for space, and showed a $(22.5\alpha+6)$-approximation
algorithm in only $\mathcal{O}(\alpha\log^{\mathcal{O}(1)}n)$ space. McGregor
and Vorotnikova [34] showed that the algorithm of Cormode et al. [12] can
achieve a $(\alpha+2)$-approximation via a tighter analysis. For turnstile
streams, Chitnis et al. [9] designed a $(22.5\alpha+6)$-approximation
algorithm using $\tilde{\mathcal{O}}(\alpha n^{4/5})$ space. Bury et al. [5]
improved the approximation ratio to $(\alpha+2)$, their algorithm requires
$\tilde{\mathcal{O}}(\alpha n^{4/5})$ space in edge-arrival streams, but only
$\mathcal{O}(\log n)$ in vertex-arrival streams.

Switching the arrival order from arbitrary to random, researchers have
developed algorithms for domination number $\gamma$ and independence number
$\beta$. Monemizadeh et al. [37] converted known constant-time RAM-model
approximation algorithms into constant-space streaming algorithms. Their
algorithm approximates the domination number in bounded-degree graphs, with an
additive error term of ${\varepsilon}n$. Peng and Sohler [41] further extended
this result to graphs of bounded average degree. They also showed that in
planar graphs, independence number $\beta$ can be
$(1+{\varepsilon})$-approximated using constant, but still massive, space,
i.e.,
$\mathcal{O}(2^{(1/{\varepsilon})^{(1/{\varepsilon})^{\log^{\mathcal{O}(1)}(1/{\varepsilon})}}})$.

Another line of research approximates independence number via the Caro-Wei
Bound. Halldórsson et al. [22] studied general hypergraphs and gave a one-pass
insertion-only streaming algorithm in $\mathcal{O}(n)$ space, outputting, in
expectation, an independent set with size at least the Caro-Wei bound,
$\lambda$; their algorithm suits the _online streaming_ model. Cormode et al.
[10] designed an algorithm that $(1\pm{\varepsilon})$-approximates $\lambda$
with constant success probability in
$\mathcal{O}({\varepsilon}^{-2}\bar{d}\log n)$ space. When the input is a
vertex-arrival stream with very large average degree, they achieved an $(\log
n)$-approximation with $\mathcal{O}(\log^{3}n)$ space. They also showed a
nearly tight lower bound: every randomized one-pass algorithm with constant
error probability requires $\Omega({{\varepsilon}^{-2}}{\bar{d}})$ space to
$(1\pm{\varepsilon})$-approximate $\lambda$.

Meanwhile, Chitnis and Cormode [8] adapted the lower-bound reduction technique
from Assadi et al. [2] and showed that, for graphs with arboricity $\alpha+2$,
for $\alpha\geq 1$, every randomized ${\alpha}/{32}$-approximation algorithm
for minimum dominating set requires $\Omega(n)$ space. This lower bound holds
even under the vertex-arrival model.

Simplifying the graph does not make things significantly easier. When the
input is a tree, several $(2+{\varepsilon})$-approximation algorithms are
known for matching number, $\phi$. Esfandiari et al. [18] designed an
$\tilde{\mathcal{O}}(\sqrt{n})$-space algorithm for insertion-only streams,
where $\tilde{\mathcal{O}}$ notation suppresses a poly-logarithmic factor. The
space was further reduced to $\log^{\mathcal{O}(1)}n$ by Cormode et al. [12],
while Bury et al. [5] generalized it to turnstile streams.

There is relatively little research on independent set and dominating set in
trees or forests. Esfandiari et al. [18] established space lower bounds for
estimating $\phi$ in a forest: every $1$-pass randomized streaming
approximation algorithm with factor better than $3/2$ needs $\Omega(\sqrt{n})$
space. Adapting their approach gives other lower bounds: $\Omega(\sqrt{n})$
bits are required to approximate $\beta$ better than $4/3$, and $\gamma$
better than $3/2$.

###  1.2 Our Results

We design new sublinear-space streaming algorithms for estimating $\beta$,
$\gamma$, $\phi$ in sparse graphs. With such little space, parameter
estimation itself is of considerable importance. Our results fall into two
categories. First, approximating independent set via the Caro-Wei bound in
bounded-average-degree graphs111This includes planar graphs, bounded
treewidth, bounded genus, $H$-minor-free, etc.. Second, approximating
parameters on streamed forests.

##### Approximating the Caro-Wei Bound ($\lambda$)

Boppana et al. [4] show that $\lambda$ is at least the Turán Bound [44], i.e.,
$\beta\geq\lambda\geq{n}/(\bar{d}+1)$, indicating every
$\mathcal{O}(1)$-estimate of $\lambda$ is a
$\mathcal{O}(\bar{d})$-approximation of $\beta$. We hence approximate $\beta$
in bounded-average-degree graphs; we summarize results in Table 1.

With a random permutation of vertices, there is a known offline algorithm for
estimating $\lambda$. Our algorithm, Caraway, simulates such a permutation via
hash functions drawn uniformly at random from an ${\varepsilon}$-min-wise hash
family. Let ${\varepsilon}$ be the approximation error _rate_ 222The _relative
error_ between the estimate and the actual value.. For graphs with average
degree $\bar{d}$ and max degree
$\Delta\in\mathcal{O}({\varepsilon}^{2}\bar{d}^{-3}n)$, Caraway
$(1\pm{\varepsilon})$-approximates $\lambda$ in an arbitrary-order edge-
arrival stream. It fails with probability at most $\delta$, and uses working
space $\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log n\cdot\log\delta^{-1})$. By
allowing $\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log n\cdot\log\delta^{-1})$
additional, write-only, _solution space_ to store the output, the modified
algorithm, Caraway1, reports an actual solution set in the _online streaming_
model with $\mathcal{O}(\log{\varepsilon}^{-1})$ update time. The max-degree
constraint is required only to bound the failure probability, $\delta$ for
these two algorithms; if an _in-expectation_ bound suffices, this constraint
can be disregarded.

Our other modified algorithm, Caraway2, removes the max-degree constraint
entirely, but requires more space. Failing with low probability, Caraway2
returns a $(1\pm{\varepsilon})$-approximation using
$\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2}\log^{2}n)$ space. Since post-
processing is required, Caraway2 works in the standard streaming model, but
not in the _online streaming_ model. Additionally, if the stream is vertex-
arrival and random-order, Caraway can be modified to use only
$\mathcal{O}(\log(\bar{d}{\varepsilon}^{-1})\cdot\log\delta^{-1})$ space.

Bounding _rate_ ${\varepsilon}$ is non-trivial: there is positive correlation
between vertices being in the sample whence we estimate $\lambda$. To bound
${\varepsilon}$, we start by constraining the max degree; we also bound
${\varepsilon}$ in the offline algorithm and all its variants.

Comparison with Cormode et al. [10] : Since Cormode et al. relied on
estimating sampled vertices’ degrees, we understand their methods report the
parameter $\beta$, but not an actual independent set. In an insertion-only
stream satisfying our $\Delta$ constraint, Caraway has asymptotically the same
approximation ratio in the same space as Cormode et al. Importantly, in
_online streaming_ , Caraway1, can output an actual independent set. Moreover,
in vertex-arrival and random-order streams, Caraway requires comparatively
less space.

Comparison with Halldórsson et al. [22] : The online streaming algorithm by
Halldórsson et al. has $\mathcal{O}(\log n)$ update time and $\mathcal{O}(n)$
working space. Caraway1 has faster update time,
$\mathcal{O}(\log{\varepsilon}^{-1})$, and less working space,
$\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log n\cdot\log\delta^{-1})$. Besides,
our estimate is within an error rate, ${\varepsilon}$, with a guaranteed
constant probability; there is no such guarantee from Halldórsson et al.

##### Estimating $\beta,\gamma$ and $\phi$ on Forests

Table 2 has results on streamed forests. Esfandiari et al. [18] showed it is
non-trivial to estimate fundamental graph parameters (e.g., $\beta$, $\gamma$,
$\phi$) in a one-pass streamed forest 333$\Omega(\sqrt{n})$ (or $\Omega(n)$)
space is required for randomized (or deterministic) algorithms.). We trade off
approximation ratio for space and number of passes, and obtain two results
classes.

Table 1: Streaming Caro-Wei Bound approximation. _Arrival_ is Edge for edge-arrival or Vertex for vertex-arrival. _Type_ is Insert for insertion-only or Turns for turnstile. _Order_ is Arb for arbitrary or Ran for random. _Online_ is “Yes” for _online streaming_ algorithm. Theorems marked as ‘∗’ have the max-degree constraint, which can be removed if an _in-expectation guarantee_ suffices. Constants $c\in(0,1)$ and $c^{\prime}>1$.  Arrival | Type | Order | Factor | (Work) Space | Online | Success Prob | Reference
---|---|---|---|---|---|---|---
Edge | Insert | Arb | 1 | $\mathcal{O}(n)$ | Yes | Expected | [22]
Edge | Turns | Arb | $(1\pm{\varepsilon})$ | $\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log n)$ | No | $c$ | [10]
Edge | Insert | Arb | $(1\pm{\varepsilon})$ | $\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log n)$ | No | $c$ | Theorem 6∗
Edge | Insert | Arb | $(1\pm{\varepsilon})$ | $\mathcal{O}(\log{\varepsilon}^{-1}\log n)$ | Yes | $c$ | Theorem 7∗
Edge | Insert | Arb | $(1\pm{\varepsilon})$ | $\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2}\log^{2}n)$ | No | $n^{-c^{\prime}}$ | Theorem 8
Vertex | Insert | Ran | $(1\pm{\varepsilon})$ | $\mathcal{O}(\log(\bar{d}{\varepsilon}^{-1}))$ | No | $c$ | Theorem 9∗
Either | Either | Arb | $c$ | $\Omega({\bar{d}}/{c^{2}})$ | - | $c$ | [10]
Table 2: Estimating $\gamma,\beta$, and $\phi$ in streamed forests. All succeed with high probability. Problem | Arrival | Type | Order | Pass | Factor | Space | Reference
---|---|---|---|---|---|---|---
$\gamma$ | Edge | Turns | Arb | 1 | $3(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ | Theorem 18
$\gamma$ | Edge | Turns | Arb | 2 | $2(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 19
$\gamma$ | Any | Any | Arb | 1 | $3/2-{\varepsilon}$ | $\Omega(\sqrt{n})$ | [18]
$\beta$ | Edge | Turns | Arb | 1 | $3/2(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ | Theorem 16
$\beta$ | Edge | Turns | Arb | 2 | $4/3(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 17
$\beta$ | Any | Any | Arb | 1 | $4/3-{\varepsilon}$ | $\Omega(\sqrt{n})$ | [18]
$\phi$ | Edge | Insert | Arb | 1 | $2(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | [18]
$\phi$ | Edge | Insert | Arb | 1 | $2(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ | [12]
$\phi$ | Edge | Turns | Arb | 1 | $2(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ |  [6], Theorem 20
$\phi$ | Edge | Turns | Arb | 2 | $3/2(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 21
$\phi$ | Any | Any | Arb | 1 | $3/2-{\varepsilon}$ | $\Omega(\sqrt{n})$ | [18]

First, one-pass $\log^{\mathcal{O}(1)}n$-space algorithms, which relying on
approximating both the numbers of leaves and non-leaf vertices in a stream. We
have

  * •

a $3/2\cdot(1\pm\epsilon)$-approximation for $\beta$;

  * •

a $3\cdot(1\pm\epsilon)$-approximation for $\gamma$;

  * •

a $2\cdot(1\pm\epsilon)$-approximation for $\phi$.

Second, two-pass $\tilde{\mathcal{O}}(\sqrt{n})$-space
algorithms444$\tilde{\mathcal{O}}$ suppresses the poly-logarithmic factor in
the bound.: We further narrow the gap between the upper and lower bounds [18]:

  * •

a $4/3\cdot(1\pm\epsilon)$-approximation algorithm for $\beta$;

  * •

a $2\cdot(1\pm\epsilon)$-approximation algorithm for $\gamma$;

  * •

a $3/2\cdot(1\pm\epsilon)$-approximation algorithm for $\phi$.

Our innovation is introducing the notion of support vertices from structural
graph theory [15]. A _support vertex_ is one that is adjacent to one or more
leaves: an approximate count could be a key component of streaming graph
algorithms.

##  2 Preliminaries

Given a set of vertices in $G$, $S$, let $N(S)$ be the neighbors of $S$
(excluding $S$), and $N[S]$ be $S\cup N(S)$. Let $\Delta$ be the max degree
and $\bar{d}$ be the average degree of $G$, and $d(v)$ be the degree of vertex
$v$. $\mathit{Deg}_{i}(G)$ is the set of vertices with $d(v)=i$, while
$\mathit{Deg}_{\geq i}(G)$ is the set with $d(v)\geq i$. A support vertex [15]
is a vertex adjacent to at least one leaf. We denote the set of support
vertices by $\mathit{Supp}(G)$.

###  2.1 Fundamental Streaming Algorithms

We assume vertices are $[n]=\\{1,2,\ldots,n\\}$, and that $n$ is known in
advance. Second, our results are developed for certain graph classes, hence we
assume that at the _end_ of the stream, the graph is guaranteed to be in the
target class.

We employ several streaming primitives. Consider a vector $x\in\mathbb{R}^{n}$
whose coordinates are updated by a turnstile stream with each update in the
range $[-M,M]$. Let $x_{i}$ be the final value of coordinate $i$. For
$p~{}>~{}0$, the $L_{p}$ norm of $x$ is $\|x\|_{p}=(\sum_{i=1}^{n}\lvert
x_{i}\rvert^{p})^{1/p}$. The $L_{0}$ _norm_ is
$\|x\|_{0}=(\sum_{i=1}^{n}\lvert x_{i}\rvert^{0})$. Both _norms_ can be
$(1\pm{\varepsilon})$-approximated in streams in small space.

######  Theorem 1.

[28] For $p\in(0,2)$ and ${\varepsilon},\delta\in(0,1)$, there is an algorithm
that $(1\pm{\varepsilon})$-approximates $\|x\|_{p}$ with probability at least
$1-\delta$ and $\mathcal{O}({\varepsilon}^{-2}\log(mM)\log\delta^{-1})$ space
usage. Both update and reporting time are in
$\tilde{\mathcal{O}}({\varepsilon}^{-2}\log\delta^{-1})$.

######  Theorem 2.

[29] Given ${\varepsilon},\delta\in(0,1)$, there is an algorithm that, with
probability at least $1-\delta$, $(1\pm{\varepsilon})$-approximates
$\|x\|_{0}$. It has an update and reporting time of
$\mathcal{O}(\log\delta^{-1})$, and uses space:

$\mathcal{O}({\varepsilon}^{-2}\log(\delta^{-1})\log(n)(\log(1/{\varepsilon})~{}+~{}\log\log(mM))).$

Given $k\leq n$, $x$ is  _$k$ -sparse_ if it has at most $k$ non-zero
coordinates.

######  Theorem 3.

[11] Given $k$ and $\delta\in(0,1)$, there is an algorithm that recovers a
$k$-sparse vector exactly with probability $1-\delta$ and space usage
$\mathcal{O}(k\log n\cdot\log(k/\delta))$.

We focus on _heavy hitters_ that are coordinates of vector $x$ with $\lvert
x_{i}\rvert\geq{\varepsilon}\|x\|_{1}$.

######  Theorem 4.

[13] Given ${\varepsilon},\tau\in(0,1)$, there is an algorithm that outputs
all items with frequency at least $({\varepsilon}+\tau)\lVert x\rVert_{1}$,
and with probability $1-\delta$ outputs no items with frequency less than
$\tau\lVert x\rVert_{1}$. It has update time $\mathcal{O}(\log
n\cdot\log({2\log n}/{(\delta\tau)}))$ and query time
$\mathcal{O}({\varepsilon}^{-1})$, and uses
$\mathcal{O}({\varepsilon}^{-1}\log n\cdot\log(2\log n/(\delta\tau)))$ space.

###  2.2 $\bf{{\varepsilon}}$-min-wise Hash Functions

To simulate uniform-at-random selection, we invoke carefully chosen hash
families. A family of hash functions, $\mathcal{H}=\\{h:[n]\rightarrow[m]\\}$,
is “${\varepsilon}$-min-wise” if for every $A\subset[n]$ and $x\in[n]\setminus
A$,

$\Pr_{h\in\mathcal{H}}[\forall a\in
A,h(x)<h(a)]=\frac{1\pm{\varepsilon}}{\lvert A\rvert+1}\,.$

Indyk [25] showed that the ${\varepsilon}$-min-wise property can be achieved
via a $\mathcal{O}(\log{\varepsilon}^{-1})$-wise hash family, under the
constraints that $\lvert A\rvert\in\mathcal{O}({\varepsilon}m)$. Its space
usage is $\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log m)$ and its computation
time is $\mathcal{O}(\log{\varepsilon}^{-1})$.

###  2.3 Extension of Chernoff-Hoeffding inequality

Panconesi and Srinivasan [40] extended the Chernoff-Hoeffding inequality to
negatively correlated Boolean random variables as follows:

######  Theorem 5.

[40] For $r$ negatively correlated Boolean random variables
$X_{1},\dots,X_{r}$, let $X=\sum_{i=1}^{r}X_{i}$, $\mu=E[X]$ and $0<\delta<1$,
then

$\Pr\big{[}\lvert X-\mu\rvert\geq\delta\mu\big{]}\leq
2e^{-\frac{\mu\delta^{2}}{2}}\,.$

##  3 Estimating $\beta$ via the Caro-Wei Bound

In this section, we introduce efficient streaming algorithms to estimate the
independence number, $\beta$ in graphs with bounded average degree. A
_folklore_ offline greedy algorithm returns an independent set whose size is
in expectation the Caro-Wei Bound, $\lambda$. Given a uniform-at-random
permutation $\pi$ of $V$, the greedy algorithm adds vertex $v$ to the solution
whenever $v$ is _earlier_ in $\pi$ than all $v$’s neighbors. Storing $\pi$
explicitly requires $\Omega(n\log n)$ bits, not sublinear, so disallowed here.

We instead simulate a random permutation via function $h$ drawn randomly from
an ${\varepsilon}$-min-wise hash-family, $\mathcal{H}$. Vertex $v$ is added
whenever its $h(v)$ is less than all its neighbors’ hash values. Family
$\mathcal{H}$ ensures the probability $v$ has smallest hash is approximately
proportional to $\deg(v)$. As $\deg(v)$ could be $\Theta(n)$, we rely instead
on standard sampling and recovery techniques in our algorithm, Caraway, see
Algorithm 1. The co-domain of $h$ in Caraway is $[n^{3}]$ for two reasons: (i)
with high probability, there are no colliding pairs; (ii) we assume
${\varepsilon}\in\omega(n^{-2})$, so the ${\varepsilon}$-min-wise property
applies to every subset of size $\geq n$.

Algorithm 1 Caraway, estimating Caro-Wei bound

1:Input: Average degree, $\bar{d}$, error rate, ${\varepsilon}$.

2:Initialization: $p\leftarrow 4(\bar{d}+1)/({\varepsilon}^{2}n)$

3:$S\leftarrow pn\text{ vertices sampled uniformly at random from }[n]$

4:Select uniformly at random $h\in\mathcal{H}$, ${\varepsilon}$-min-wise hash
functions: $[n]\rightarrow[n^{3}]$

5:for all $e=(u,v)\text{ in the stream}$ do

6: if $(u\in S)\wedge(h(u)\geq h(v))$ then

7: Remove $u$ from $S$

8: if $(v\in S)\wedge(h(v)\geq h(u))$ then

9: Remove $v$ from $S$

10:return $\widehat{\lambda}\leftarrow\lvert S\rvert/p$

######  Theorem 6.

Given ${\varepsilon}\in(0,1)$, if
$\Delta~{}\leq~{}{{\varepsilon}^{2}~{}n}/({3~{}(\bar{d}+1)^{3}})$, in an
insertion-only stream, Caraway $(1\pm{\varepsilon})$-approximates $\lambda$
w.p. $2/3$ in work space $\mathcal{O}(\bar{d}\,{\varepsilon}^{-2}\log n)$.

To prove Theorem 6, we start with a result on the expectation of
$\widehat{\lambda}$.

######  Lemma 1.

$E[\widehat{\lambda}]=(1\pm{\varepsilon})\,\lambda$.

###### Proof.

Let binary random variables $X_{v}$ denote whether vertex $v$ is sampled in
$S$ and not removed during the stream. That is, $X_{v}=1$ if $v\in S$ at the
end of the stream. Let $X=\sum_{v\in V(G)}X_{v}$, clearly, $X=\lvert S\rvert$
at the end. It is not hard to see that $X_{v}=1$ if and only if $v$ is sampled
and $v$ has the smallest hash value in $N[v]$. According to the property of
${\varepsilon}$-min-wise hash families, $v$ has the smallest hash value in
$N[v]$ with probability $\frac{1\pm{\varepsilon}}{\lvert N[v]\rvert}$. By the
construction of algorithm, $v$ is sampled with probability $p$. Since these
two events are independent, the probability that $X_{v}=1$ is
$(1\pm{\varepsilon})\,\frac{p}{d(v)+1}$. Hence, by the linearity of
expectation, we have

$E[\lvert S\rvert]=\sum_{v\in V(G)}E[X_{v}]=p\sum_{v\in
V(G)}\frac{1\pm{\varepsilon}}{d(v)+1}=(1\pm{\varepsilon})\,p\,\lambda\,.$

Hence, $E[\widehat{\lambda}]=E[\frac{\lvert
S\rvert}{p}]=(1\pm{\varepsilon})\,\lambda$. ∎

We show that, with constant probability, estimate $\widehat{\lambda}$ is no
more than a $1\pm{\varepsilon}$ factor away from its mean,
$E[\widehat{\lambda}]$. Let $X_{v}$ be an indicator variable for the event
that $v$ is both sampled in, and not removed from, $S$. Let $X=\sum_{v\in
V}X_{v}$. Since some pairs of $X_{v}$ and $X_{u}$ are positively correlated,
to estimate $X$, we cannot directly apply a Chernoff(-like) bound. There are
three cases to consider.

  * •

Vertices $u$ and $v$ are adjacent: $u\in N[v]$ and $v\in N[u]$. If $X_{u}$ is
$1$, wlog, we know that $X_{v}$ is $0$. Hence $X_{v}$ and $X_{u}$ are
negatively correlated.

  * •

Vertices $u$ and $v$ are not adjacent, but share at least one neighbor.
Consider one such common neighbor, $w$, i.e., $w\in N[u]\cap N[v]$. Let
$x<N(x)$ denote $x$ having a smaller hash value than all elements in $N(x)$.
Knowing $u<N(u)$ implies $h(v)<h(w)$ is more likely, and hence $v<N(v)$ is
more likely, hence $X_{v}$ and $X_{u}$ are positively correlated, shown in
Lemma 2.

  * •

All other cases: $X_{v}$ and $X_{u}$ are independent (see Lemma 2).

######  Lemma 2.

Let $x$ and $y$ be non-adjacent vertices with $|N(x)\cap N(y)|=k$,
$|N(x)\setminus N(y)|=l$, and $|N(y)\setminus N(x)|=r$. From a uniform random
permutation, we have $\Pr[y<N(y)\mid x<N(x)]={(l+r+2k+2)}/[(r+k+1)(l+k+r+2)]$.
This also holds within a factor $1\pm{\varepsilon}$ when the permutation is
generated from a hash function from a ${\varepsilon}$-min-wise family.

###### Proof.

To begin with, we prove the statement with uniform random permutation.
Consider $n=l+k+r+2$ vertices $x,y$, $w_{1},\ldots,w_{l}$,
$u_{1},\ldots,u_{k}$, and $v_{1},\ldots,v_{r}$. For simplicity, we use $W$,
$U$, and $V$ to denote $\\{w_{1},\ldots,w_{l}\\}$, $\\{u_{1},\ldots,u_{k}\\}$,
and $\\{v_{1},\ldots,v_{r}\\}$. Note that $x$ has degree $l+k$, $y$ has degree
$k+r$, $x$ and $y$ are not adjacent and they share $k$ neighbors, i.e.,
$N(x)=\\{W\cup U\\}$ and $N(y)=\\{U\cup V\\}$.

We use $x<N(x)$ if $x$ has the smallest order among $N[x]$ in the permutation.
Note that since we assume uniform random permutation, $\Pr[x<N(x)]=1/(\lvert
N(x)\rvert+1)=1/(l+k+1)$. Consider the event $X<N(X)$ and $Y<N(Y)$, we have
two cases:

  * •

$x$, followed by zero or more $W$, $y$, followed by a mixture of the rest of
$W$, $V$, and $U$.

  * •

$y$, followed by zero or more $V$, $x$, followed by a mixture of $W$, the rest
of $V$, and $U$.

By the uniform random permutation, the _first_ event occurs with probability

$\frac{1}{l+k+r+2}\cdot\frac{1}{k+r+1}\,,$

where the first factor is the probability of $x<\\{y\\}\cup W\cup V\cup U$,
and the second factor is the probability of $y<V\cup U$, regardless of how it
relates with vertices in $W$. Note these two events are independent of each
other, since knowing $x$ being the smallest across $y,W,U,V$ does not reveal
anything about the ordering inside of $y,W,U,V$. By similar argument, the
_second_ event occurs with probability

$\frac{1}{l+k+r+2}\cdot\frac{1}{l+k+1}\,.$

Summing over the two cases, we have

$\displaystyle\Pr[y<N(y)\wedge x<N(x)]$
$\displaystyle=\frac{1}{l+k+r+2}\cdot\frac{1}{k+r+1}+\frac{1}{l+k+r+2}\cdot\frac{1}{l+k+1}$
$\displaystyle=\frac{l+2k+r+2}{(l+k+r+2)(k+r+1)(l+k+1)}$

Finally, the conditional probability can be calculated as:

$\displaystyle\Pr[y<N(y)\mid x<N(x)]$ $\displaystyle=\frac{\Pr[y<N(y)\wedge
x<N(x)]}{\Pr[x<N(x)]}$ (1)
$\displaystyle=\frac{(l+r+2k+2)}{(l+k+r+2)(k+r+1)}\,.$

In a permutation generated from a hash function from a ${\varepsilon}$-min-
wise family, the equation above also holds within a factor
$1\pm{\varepsilon}$: it relies only the probability of an element being the
smallest.

So far, we assume uniform random permutation, but an analogous claim holds
with ${\varepsilon}$-min-wise property, since we only consider the probability
of an element being the smallest. The proof of ${\varepsilon}$-min-wise
property has similar structure, except we need to take $1\pm{\varepsilon}$
into account every time we calculate the probability of an element being
smallest. We also observe that the statement “knowing $x$ being the smallest
across $y,W,U,V$ does not reveal anything about the ordering inside of
$y,W,U,V$” requires a small amount of extra independence in the
$\mathcal{O}(\log{\varepsilon}^{-1})$-wise hash function. This has no effect
on the asymptotic space bound for the hash function.

Therefore, we have $\Pr[x<N(x)]=(1\pm\epsilon)/(l+k+1)$ and

$\displaystyle\Pr[y<N(y)\wedge x<N(x)]$
$\displaystyle=\frac{1\pm{\varepsilon}}{l+k+r+2}\cdot\frac{1\pm{\varepsilon}}{k+r+1}+\frac{1\pm{\varepsilon}}{l+k+r+2}\cdot\frac{1\pm{\varepsilon}}{l+k+1}$
$\displaystyle=(1\pm{\varepsilon})^{2}\frac{l+2k+r+2}{(l+k+r+2)(k+r+1)(l+k+1)}\,.$

And, finally,

$\displaystyle\Pr[y<N(y)\mid x<N(x)]$ $\displaystyle=\frac{\Pr[y<N(y)\wedge
x<N(x)]}{\Pr[x<N(x)]}$ (2)
$\displaystyle=(1\pm{\varepsilon})\frac{(l+r+2k+2)}{(l+k+r+2)(k+r+1)}\,.$

Hence, if $k=0$, then $\Pr[y<N(y)\mid x<N(x)]={1}/(r+1)=\Pr[y<N(y)]$. However,
if $k>0$, then $\Pr[y<N(y)\mid x<N(x)]>{1}/(r+k+1)$. So $x<N(x)$ and $y<N(y)$
are positively correlated iff $x$ and $y$ have some common neighbor. ∎

With a Chernoff-type bound unavailable, we bound the variance of
$\widehat{\lambda}$, and apply Chebyshev’s inequality: recall that
$\text{Var}(\widehat{\lambda})=\text{Var}({\lvert
S\rvert}/{p})=\text{Var}(X)$.

######  Lemma 3.

If $\Delta\leq{{\varepsilon}^{2}n}/(3(\bar{d}+1)^{3})$ and
$p\geq{4(\bar{d}+1)}/({\varepsilon}^{2}n)$, then
$\text{Var}(X)\leq{{\varepsilon}^{2}E^{2}[X]}/{3}$.

###### Proof.

We persist with the binary random variables from the proof of Lemma 1. In the
proof of Lemma 1, we show that
$\Pr[X_{v}=1]=\frac{(1\pm{\varepsilon})p}{d(v)+1}$. For simplicity, we ignore
the $(1\pm{\varepsilon})$ factor in the following analysis, that is,
$\Pr[X_{v}=1]=\frac{p}{d(v)+1}$; the same analysis555Another convenient
approach is to let $p^{\prime}$ be some value in
$[1-{\varepsilon},1+{\varepsilon}]$ and work with $p^{\prime}$. holds without
removing $(1\pm{\varepsilon})$. For each $X_{v}$, we have

$\text{Var}(X_{v})=E[X_{v}^{2}]-E^{2}[X_{v}]<\frac{p}{d(v)+1}(1-\frac{p}{d(v)+1})<\frac{p}{d(v)+1}$

For non-adjacent vertices $i$ and $j$ share $k\geq 0$ common neighbors, the
covariance between $X_{i}$ and $X_{j}$ is

$\displaystyle\text{Cov}(X_{i},X_{j}\mid(i,j)\notin E)$ (3)
$\displaystyle=E[X_{i}X_{j}]-E[X_{i}]E[X_{j}]$
$\displaystyle=\Pr[X_{i}=1\wedge X_{j}=1]-\Pr[X_{i}=1]\Pr[X_{j}=1]$
$\displaystyle=\Pr[X_{i}=1\mid X_{j}=1]\Pr[X_{j}=1]-\Pr[X_{i}=1]\Pr[X_{j}=1]$
$\displaystyle=(\frac{p(d(i)+d(j)+2)}{(d(i)+1)(d(i)+d(j)-l+2)}-\frac{p}{d(i)+1})\frac{p}{d(j)+1}$
$\displaystyle=\frac{p^{2}l}{(d(i)+d(j)-l+2)(d(i)+1)(d(j)+1)}\,,$

where the second-last equality arises from Equation (1), where we set
$d(i)=l+k$ and $d(j)=k+r$. It is not hard to see that Equation (LABEL:eq:cov)
is a constraint function subject to $d(i)\geq 1$, $d(j)\geq 1$, and
$k\leq\min\\{d(i),d(j)\\}$. This function has global maximum at
$\frac{p^{2}k}{(k+1)^{2}(k+2)}$ when $k=d(i)=d(j)$ for different values of
$d(i)$ and $d(j)$, which is maximized at $\frac{p^{2}}{12}$ when $k=1$. As
indicated in Equation (2), when considering ${\varepsilon}$-min-wise property
instead of uniform random permutation, the global maximum is
$\frac{(1\pm\epsilon)p^{2}}{12}\leq\frac{p^{2}}{8}$ if ${\varepsilon}<1/2$.

And for adjacent vertices $i$ and $j$, $X_{i}$ and $X_{j}$ are strongly
negatively correlated, as $X_{i}=1$ implies $X_{j}=0$. Hence,

$\displaystyle\text{Cov}(X_{i},X_{j}\mid(i,j)\in
E)=E[X_{i}X_{j}]-E[X_{i}]E[X_{j}]<0$

Let $P$ be the number of vertex pairs that share at least one common neighbor.
Assume the vertices are labeled from $1$ to $n$, by variance equation for the
sum of correlated variables, we have (for simplicity, we sometimes abbreviate
$1\leq i<j\leq n$ as $i<j$),

$\displaystyle\text{Var}(X)$
$\displaystyle=\sum_{i=1}^{n}\text{Var}(X_{i})+2\sum_{i<j}\text{Cov}(X_{i},X_{j})$
(4) $\displaystyle<\sum_{i=1}^{n}\text{Var}(X_{i})+2\sum_{i<j\wedge(i,j)\notin
E}\text{Cov}(X_{i},X_{j})$
$\displaystyle<\sum_{i=1}^{n}\frac{p}{d(i)+1}+2\sum_{i<j\wedge(i,j)\notin
E}\frac{p^{2}k}{(k+1)^{2}(k+2)}$ $\displaystyle\leq
p\,\lambda+2p^{2}\frac{P}{8}$

Note that each vertex $v$ introduces at most
$\frac{d_{v}(d_{v}-1)}{2}\leq\frac{d_{v}^{2}}{2}$ new pairs of vertices that
share a common neighbor, i.e., $v$. Thus, $P\leq\frac{1}{2}\sum_{v\in
V(G)}d_{v}^{2}$. Since
$\Delta\leq\frac{{\varepsilon}^{2}n}{3(\bar{d}+1)^{3}}$, we have

$\displaystyle\sum_{v\in
V(G)}d_{v}^{2}\leq\Delta^{2}\frac{\bar{d}n}{\Delta}+(n-\frac{\bar{d}n}{\Delta})$
$\displaystyle<(\Delta\bar{d}+1)n$ (5)
$\displaystyle\leq(\frac{{\varepsilon}^{2}n\bar{d}}{3(\bar{d}+1)^{3}}+1)n$
$\displaystyle<\frac{{\varepsilon}^{2}n^{2}}{3(\bar{d}+1)^{2}}+n$
$\displaystyle\leq\frac{{\varepsilon}^{2}n^{2}}{2(\bar{d}+1)^{2}}\,,$

where the last inequality holds when
$n\geq\frac{\sqrt{6}(\bar{d}+1)}{{\varepsilon}}$. And the first inequality is
because given the maximum degree $\Delta$ and a sufficiently large $n$, the
term $\sum_{v\in V(G)}d_{v}^{2}$ is maximized when the degree distribution is
highly biased. That is, when there are around $\frac{\bar{d}n}{\Delta}$
vertices with maximum degree $\Delta$, while the rest of vertices have degree
1 (as the graph is assumed to be connected).

Finally, combining Equation (4) and (5), we have

$\displaystyle\text{Var}(X)\leq p\,\lambda+2p^{2}\frac{P}{8}$
$\displaystyle\leq
p\,\lambda+p^{2}\frac{{\varepsilon}^{2}n^{2}}{16(\bar{d}+1)^{2}}$
$\displaystyle\leq p\,\lambda+p^{2}\frac{{\varepsilon}^{2}\lambda^{2}}{16}$
$\displaystyle=E[X]+\frac{{\varepsilon}^{2}E^{2}[X]}{16}$
$\displaystyle\leq\frac{{\varepsilon}^{2}E^{2}[X]}{3}$

where the third inequality holds because the Turán Bound is at most the Caro-
Wei Bound, i.e., $\frac{n}{\bar{d}+1}\leq\sum_{v\in
V(G)}\frac{1}{d(v)+1}=\lambda$ (see [4] for a proof). The inequality in the
second-last line arises from $E[X]=p\lambda$. And the last inequality holds if
$E[X]\geq\frac{16}{7{\varepsilon}^{2}}$; since we have assumed that
$p\geq\frac{4(\bar{d}+1)}{{\varepsilon}^{2}n}$ and
$\lambda\geq\frac{n}{\bar{d}+1}$,
$E[X]=p\lambda\geq\frac{4}{{\varepsilon}^{2}}$, the inequality follows. ∎

With Lemmas 1, 2 and 3, we prove Theorem 6.

###### Proof.

From Lemma 1 and Lemma 3, the expectation of the returned result,
$\widehat{\lambda}$, is $(1\pm{\varepsilon})\lambda$, and
$\text{Var}(X)\leq\frac{{\varepsilon}^{2}E^{2}[X]}{3}$. Hence, by Chebyshev’s
inequality,

$\displaystyle\Pr\big{[}\lvert\widehat{\lambda}-\lambda\rvert\geq
3{\varepsilon}\lambda\big{]}\leq\Pr\big{[}\lvert\widehat{\lambda}-E[\widehat{\lambda}]\rvert\geq{\varepsilon}E[\widehat{\lambda}]\big{]}=\Pr\big{[}\lvert
X-E[X]\rvert\geq{\varepsilon}E[X]\big{]}\leq\frac{1}{3}\,,$

where the first inequality holds because ${\varepsilon}<1$ so that
$(1+{\varepsilon})^{2}<(1+3{\varepsilon})$ and
$(1-{\varepsilon})^{2}>(1-3{\varepsilon})$. Therefore, the algorithm succeeds
with probability at least $2/3$.

The algorithm stores an ${\varepsilon}$-min-wise hash function and
$\mathcal{O}(\bar{d}{\varepsilon}^{-2})$ vertices. The hash function takes
$\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log n)$ bits to store, and each
vertex $v$ takes $\mathcal{O}(\log n)$ bits to store. Therefore, the total
space usage is
$\mathcal{O}((\bar{d}{\varepsilon}^{-2}+\log{\varepsilon}^{-1})\log
n)=\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log n)$. ∎

Returning the median of several instances, the success probability of
Algorithm 1 becomes $1-\delta$ in
$\mathcal{O}(\bar{d}{\varepsilon}^{-2}\log\delta^{-1}\cdot\log n)$ total
space.

The Caraway algorithm (Algorithm 1) can be further adapted to suit the
following different problem settings.

  * •

In the online streaming model, we are able to also output an actual
independent set by allowing $n$ bits of external, solution-space memory.

  * •

The condition of having a bound on the maximum degree can be removed by
excluding high-degree vertices, although this requires a post-processing stage
and is thus not an online algorithm.

  * •

In a vertex-arrival stream, with vertices in _random_ order, the algorithm
uses only $\mathcal{O}(\log(\bar{d}{\varepsilon}^{-2}))$ space.

###  3.1 Extension 1: An Independent Set in the Online Streaming model

Algorithm 1 only returns an estimate of the Caro-Wei bound, $\lambda$. It can
be easily modified to give Caraway1, which outputs an actual independent set
in the _online streaming_ model. Select $h$ uniformly at random from the
${\varepsilon}$-min-wise hash family $\mathcal{H}$. We initialise an $n$-bit
array, $A$, to true in the solution space. Upon each arriving edge $(u,v)$,
ordered such that $h(u)\leq h(v)$, we irrevocably set the $v$-th index of $A$
to false. At any time the set of indices set to true represents an independent
set with respect to the edges observed so far. By the analysis above this set
is indeed independent, its size has expected value in the range
$(1\pm{\varepsilon})\lambda$ and is concentrated around its expectation. The
working space of our algorithm is merely the space to store the hash function,
i.e., $\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log n)$. Moreover, the update
time of our algorithm is the time to compute a hash value,
$\mathcal{O}(\log{\varepsilon}^{-1})$.

######  Theorem 7.

For a graph with average degree $\bar{d}$ and max degree
$\Delta~{}\leq~{}{{\varepsilon}^{2}~{}n}/({3~{}(\bar{d}~{}+~{}1)^{3}})$,
Caraway1 is an _online streaming_ algorithm that, with probability at least
$2/3$, reports an independent set of size $1\pm{\varepsilon}$ times the Caro-
Wei bound. The working space is $\mathcal{O}(\log{\varepsilon}^{-1}\cdot\log
n)$ and update time is $\mathcal{O}(\log{\varepsilon}^{-1})$.

###### Proof.

Let a binary random variable $X_{v}$ denote whether $v$ is not removed by our
algorithm. Since $v$ is removed if and only if it does not have the smallest
hash value across $N[v]$, $\Pr[X_{v}=1]=\frac{1\pm{\varepsilon}}{d(v)+1}$. Let
$X=\sum_{v\in V(G)}X_{v}$. By the construction of the algorithm, $X$ is
exactly the size of the final solution. And

$E[X]=\sum_{v\in V(G)}\Pr[X_{v}=1]=(1\pm{\varepsilon})\sum_{v\in
V(G)}\frac{1}{d(v)+1}=(1\pm{\varepsilon})\,\lambda\,.$

Following the same proof as Lemma 3 (note: since we are not sampling, the
sampling probability $p$ in Lemma 3 can be regarded as 1), we can bound the
variance of $X$ as $\text{Var}(X)\leq\frac{{\varepsilon}^{2}E^{2}[X]}{3}$.
Applying Chebyshev’s inequality, we have

$\displaystyle\Pr\big{[}\lvert\widehat{\lambda}-\lambda\rvert\geq
3{\varepsilon}\lambda\big{]}\leq\frac{1}{3}\,,$

Hence, the algorithm fails with probability at most $1/3$.

The algorithm only uses a randomly drawn ${\varepsilon}$-min-wise hash
function, which can be stored using $\mathcal{O}(\log{\varepsilon}^{-1}\log
n)$ bits and has calculation time $\mathcal{O}(\log{\varepsilon}^{-1})$.
Hence, the space usage and the update time our algorithm is
$\mathcal{O}(\log{\varepsilon}^{-1}\log n)$ and
$\mathcal{O}(\log{\varepsilon}^{-1})$. ∎

The success probability can be boosted to $1-\delta$ by running
$\log\delta^{-1}$ independent instances simultaneously and return the maximum
result. By the union bound, the probability that all instances fail is at most
$(\frac{1}{3})^{\log\delta^{-1}}=\delta$. After boosting, the new algorithm
uses space $\mathcal{O}(\log{\varepsilon}^{-1}\log\delta^{-1}\log n)$ and has
update time $\mathcal{O}(\log{\varepsilon}^{-1}\log\delta^{-1})$.

###  3.2 Extension 2: Removing the Constraint on Max Degree

The bound $\frac{{\varepsilon}^{2}~{}n}{3~{}(\bar{d}+1)^{3}}$ on the maximum
degree, $\Delta$, is a requirement for Theorem 6. Described as Subroutine 2,
Caraway2 avoids this constraint by first removing the heavy hitters (i.e.,
high-degree vertices) in the graph. In the Caro-Wei Bound,

$\sum_{v\in V(G)}\frac{1}{1+\text{deg}(v)}\geq\lambda\,,$

high-degree vertices have very little impact on the lower bound of $\lambda$.
We formalize this observation in Lemma 4. Let $H_{\mu}$ be the set of vertices
with degree at least $\mu$ and $G_{-H_{\mu}}$ be the induced subgraph on
$V\setminus H_{\mu}$.

######  Lemma 4.

For every $\mu\geq(\bar{d}+1)/\sqrt{{\varepsilon}}$, we have
$\lambda(G)\geq\lambda(G_{-H_{\mu}})\geq(1-{\varepsilon})\lambda(G)$.

###### Proof.

The upper bound, $\lambda(G)\geq\lambda(G_{-\mathit{Deg}_{\geq\mu}})$, clearly
holds as removing vertices does not increase $\lambda$.

Given the average degree $\bar{d}$, by the Pigeonhole Principle, there are at
most $\frac{\bar{d}n}{\mu}$ vertices with degree at least $\mu$. Hence, we
have

$\displaystyle\lambda(G_{-\mathit{Deg}_{\geq\mu}})>\lambda(G)-\sum_{v\in\mathit{Deg}_{\geq\mu}}\frac{1}{d(v)+1}$
$\displaystyle\geq\lambda(G)-\frac{1}{\mu+1}\frac{\bar{d}n}{\mu}$
$\displaystyle>\lambda(G)-{\varepsilon}\frac{\bar{d}n}{(\bar{d}+1)^{2}}$
$\displaystyle\geq\lambda(G)-{\varepsilon}\lambda(G)\,,$

where the last inequality holds as the Turán Bound is at most the Caro-Wei
Bound, i.e., $\frac{n}{\bar{d}+1}\leq\sum\frac{1}{d(v)+1}=\lambda$ (see [4]
for a proof). ∎

Let $R$ be the vertices to be ignored, which should666Lemma 5 clarifies
exactly which vertices are in $R$. be those with degree at least
$(\bar{d}+1)/\sqrt{{\varepsilon}}$. Ignoring $R$, similar to Algorithm 1,
Subroutine 2 approximates $\lambda$ in the remaining graph by sampling
vertices and removing some, based on hash values. By Lemma 4, this estimate is
at most factor $1-{\varepsilon}$ away from the Caro-Wei bound of the original
graph, $G$.

We identify the high-degree vertices, $R$, via the heavy-hitter sketch, with
specific parameter settings, as described in here. Since $R$ is only reported
at the end of stream, Subroutine 2 retains all neighbors of vertices in $S$,
deferring the heavy-hitter ignoring and hash-value removal to post-processing.
If two passes are allowed, or if $R$ is provided in advance, then these two
steps can be done on-the-fly, fitting into the online streaming model. In
particular, the condition in line 6 of Algorithm 1 becomes $(u\in
S)\wedge(v\notin R)\wedge(h(u)\geq h(v))$.

Subroutine 2 Caraway2: Estimating Caro-Wei Bound without Degree Constraint

1:Input 1: the average degree, $\bar{d}$, the error rate, ${\varepsilon}$

2:Initialization: Uniformly-at-random select $h\in\mathcal{H}$, an
${\varepsilon}$-min-wise hash family from $[n]$ to $[n^{3}]$

3:$p\leftarrow 4(\bar{d}+1)/({\varepsilon}^{2}n)$

4:$S\leftarrow pn$ vertices sampled uniformly at random from $[n]$

5:for $u\in S$ do

6: $L_{u}\leftarrow\\{\\}$

7:for all $e=(u,v)$ in the stream do

8: if $u\in S$ then

9: Add $v$ to $L_{u}$

10: Perform the same operation on $v$

11: if $\sum_{u\in S}(1+\lvert L_{u}\rvert)>10\bar{d}pn$ then

12: Abort

1:Post-processing:

2:Input 2: a set of ignored vertices, $R$

3:for all $v\in R$ do

4: for all $u\in S$ do

5: $L_{u}\leftarrow L_{u}\setminus\\{v\\}$

6:for all $v\in S$ do

7: for all $u\in L_{v}$ do

8: if $h(u)<h(v)$ then

9: $S\leftarrow S\setminus\\{v\\}$

10:return $\widehat{\lambda}=\lvert S\rvert/p$

######  Lemma 5.

Suppose $R$ contains all vertices with degree at least
$\frac{{\varepsilon}^{2}~{}n}{3~{}(\bar{d}+1)^{3}}$, but no vertices with
degree less than $(\bar{d}+1)/{\sqrt{{\varepsilon}}}$. Given
${\varepsilon}\in(0,1)$, for every graph with average degree $\bar{d}$,
Subroutine 2 is an insertion-only algorithm that
$(1\pm{\varepsilon})$-approximates the Caro-Wei bound. Its work space is
$\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2}\log n)$; it succeeds with
probability at least $19/30$.

###### Proof.

By the construction of Subroutine 2, vertices in $R$ are removed from the
neighborhood list of sampled vertices (line 15 – 17). Hence, by the condition
on line 20, each sampled vertex is retained in $S$ if and only if it has the
smallest hash value across its neighbors in the subgraph after removing $R$.
Let $X_{v}$ be the binary indicator of $v$ being sampled and retained in $S$.
Since the sampling procedure and the hash function are independent,
$\Pr[X_{v}=1]=(1\pm{\varepsilon})\frac{p}{d^{\prime}(v)+1}$, where
$d^{\prime}(v)$ is the degree of $v$ after removing $R$. Let $X=\sum_{v\in
V(G)}X_{v}$. Clearly, $X=\lvert S\rvert$ at the end of stream. Let
$\lambda^{\prime}$ be the Caro-Wei bound of the subgraph after removing $R$,
by the linearity expectation, the expectation of $\widehat{\lambda^{\prime}}$
is

$E[\widehat{\lambda^{\prime}}]=E[\lvert S\rvert]/p=\frac{1}{p}\,\sum_{v\in
V(G)}E[X_{v}]=\sum_{v\in
V(G)}\frac{1\pm{\varepsilon}}{d^{\prime}(v)+1}=(1\pm{\varepsilon})\lambda^{\prime}\,,$

The variance of $\widehat{\lambda^{\prime}}$ is the same as the variance of
$X$, as $p$ is fixed. By Lemma 3, condition on $R$ contains all vertices with
degree at least $\frac{{\varepsilon}^{2}~{}n}{3~{}(\bar{d}~{}+~{}1)^{3}}$, we
have $\text{Var}(X)\leq\frac{{\varepsilon}^{2}E^{2}[X]}{3}$. Hence,

$\displaystyle\Pr\big{[}\lvert\widehat{\lambda^{\prime}}-\lambda^{\prime}\rvert\geq
3{\varepsilon}\lambda^{\prime}\big{]}\leq\Pr\big{[}\lvert
X-E[X]\rvert\geq{\varepsilon}E[X]\big{]}\leq\frac{\text{Var}(X)}{{\varepsilon}^{2}E^{2}[X]}\leq\frac{1}{3}\,.$

By Lemma 4, condition on $R$ contains no vertices with degree smaller than
${\bar{d}(\bar{d}+1)}/{\varepsilon}$,
$\lambda^{\prime}\geq(1-{\varepsilon})\lambda$. Also, the algorithm aborts if
the size of sampled vertices and their neighborhood lists are too large (line
11 – 12). Since the average degree is $\bar{d}$, in expectation, $\bar{d}pn$
vertices are stored by our algorithm. By Markov’s inequality, the probability
that the actual number of stored vertices is 10 times greater than its
expectation, $\bar{d}pn$, is at most $1/10$. Applying the union bound, the
probability that this algorithm fails or aborts is at most $11/30$.

The space usage of this algorithm is space to store the hash function, plus
the space to store sampled vertices and their neighbors. Because of our
constraints on line 11, there are at most
$\mathcal{O}(\bar{d}pn)=\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2})$ vertices
being stored, where each vertex takes $\mathcal{O}(\log n)$ bits to store. The
hash function takes $\mathcal{O}(\log{\varepsilon}^{-1}\log n)$ bits to store.
Hence, the total space usage is $\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2}\log
n)$. ∎

####  3.2.1 Identifying heavy hitters

The success of Subroutine 2 depends on identifying the set of high-degree
vertices, $R$, well. By Theorem 4, running the algorithm of Cormode and
Muthukrishnan [13] with $\psi=\tau=\frac{{\varepsilon}^{2}}{6(\bar{d}+1)^{4}}$
and $\delta=n^{-c^{\prime}}$, for some constant $c^{\prime}>1$, we obtain the
desired removal set with high probability. This heavy-hitter technique
requires $\mathcal{O}({\varepsilon}^{-1}\log^{2}n)$ space. By running
$c^{\prime}\log n$ (for some constant $c^{\prime}$) instances of Subroutine 2
concurrently, and returning the maximum result, the failure probability drops
to $n^{-c^{\prime}}$. Importantly, there is only one instance of the heavy-
hitter algorithm. The heavy-hitter algorithm is independent of Subroutine 2,
but feeds its output $R$ to every instance of Subroutine 2. Via a union bound,
the whole process’s failure probability is at most $2n^{-c^{\prime}}$.

######  Theorem 8.

Given ${\varepsilon}\in(0,1)$, for every graph with average degree $\bar{d}$,
Caraway2 is an algorithm that whp $(1\pm{\varepsilon})$-approximates the Caro-
Wei bound in $\mathcal{O}(\bar{d}^{2}{\varepsilon}^{-2}\log^{2}n)$ space.

###  3.3 Extension 3: Algorithm for Random-Order Vertex-Arrival Streams

So far, we have relied on a hash function drawn from an ${\varepsilon}$-min-
wise hash family to approximate a random permutation. However, if the stream
is vertex-arrival and random-order, the random permutation comes for free.
Moreover, we can immediately tell whether the vertex is earliest in its
neighborhood because the _convention_ is only to list prior-occurring
neighbors. Hence, it suffices to count the number of such vertices, with space
further reduced to $\mathcal{O}(\log(\bar{d}{\varepsilon}^{-1}))$ by
incrementing the counter with probability
$p=\frac{4(\bar{d}+1)}{{\varepsilon}^{2}n}$. We abort the algorithm if
$c>10pn$, which happens with probability less than $1/10$. We conclude the
following theorem:

######  Theorem 9.

Given ${\varepsilon}\in(0,1)$, for every graph with average degree $\bar{d}$
and max degree
$\Delta~{}\leq~{}\frac{{\varepsilon}^{2}~{}n}{3~{}(\bar{d}~{}+~{}1)^{3}}$,
Caraway3 is an insertion-only random-order vertex-arrival algorithm that
$(1\pm{\varepsilon})$-approximates $\lambda$. It succeeds with probability at
least $19/30$ in space $\mathcal{O}(\log(\bar{d}{\varepsilon}^{-2}))$.

###### Proof.

Firstly, note that $\widehat{\lambda}$ is an unbiased estimator of $\lambda$,
as each vertex arrives uniformly at random. Let binary random variable $X_{v}$
denote whether $c$ is incremented when $v$ arrives. That is, $X_{v}=1$ if the
neighborhood list of $v$ is empty, and the counter is increased. These two
events are independent, the former event happens with probability
$\frac{1}{d(v)+1}$, while the latter event happens with probability $p$. Let
$X=\sum_{v\in V(G)}X_{v}$. By the linearity of expectation, we have

$E[\widehat{\lambda}]=E[c]/p=E[X]/p=\frac{1}{p}\,\sum_{v\in
V(G)}E[X_{v}]=\sum_{v\in V(G)}\frac{1}{d(v)+1}=\lambda\,.$

By Lemma 3, the variance of $X$,
$\text{Var}(X)\leq\frac{{\varepsilon}^{2}E^{2}[X]}{3}$. Applying Chebyshev’s
inequality, we have

$\displaystyle\Pr\big{[}\lvert\widehat{\lambda}-\lambda\rvert\geq{\varepsilon}\lambda\big{]}=\Pr\big{[}\lvert
X-E[X]\rvert\geq{\varepsilon}E[X]\big{]}\leq\frac{\text{Var}(X)}{{\varepsilon}^{2}E^{2}[X]}\leq\frac{1}{3}\,,$

The algorithm might fail if the counter, $c$, becomes too large, i.e.,
$c>10pn$. By Markov’s inequality,

$\Pr[X\geq 10pn]\leq\frac{E[X]}{10pn}=\frac{\lambda}{10n}\leq\frac{1}{10}\,.$

Therefore, applying the union bound, the algorithm succeeds with probability
at least $1-1/3-1/10=19/30$.

The space usage of the algorithm is the size of the counter $c$. By the
construction of the algorithm, $c$ is incremented to at most $10pn$. Hence, it
can be stored in
$\mathcal{O}(\log(pn))=\mathcal{O}(\log(\bar{d}{\varepsilon}^{-2}))$ bits. ∎

Similarly, by running $\log\delta^{-1}$ independent instances concurrently and
return the maximum result, the success probability can be boosted to
$1-\delta$. This is because the probability that all instances fail is at most
$(\frac{11}{30})^{\log\delta^{-1}}=\delta$. The space usage of the new
algorithm after boosting is
$\mathcal{O}(\log(\bar{d}{\varepsilon}^{-2})\log\delta^{-1})$.

##  4 Sublinear-space Streaming Algorithms for Approximating
Graph Parameters in Forests

We now describe our sublinear-space streaming algorithms for approximating
graph parameters when the input graph is a forest777Unless otherwise stated,
we assume that the input forest has no isolated vertices.. Our algorithms work
for turnstile edge-arrival streams. For each graph parameter, we design two
algorithms: a $1$-pass algorithm using $\log^{\mathcal{O}(1)}n$ space, and a
$2$-pass algorithm using $\tilde{\mathcal{O}}(\sqrt{n})$ space, with better
approximation ratio (see Table 3).

Table 3: Turnstile edge-arrival streaming algorithms for approximating $\gamma$, $\beta$, and $\phi$ in forests. Each succeeds with high probability. Problem | Number of Passes | Approximation Factor | Space | Reference
---|---|---|---|---
$\beta$ | 1 | $3/2\cdot(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ | Theorem 16
$\beta$ | 2 | $4/3\cdot(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 17
$\gamma$ | 1 | $3\cdot(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ | Theorem 18
$\gamma$ | 2 | $2\cdot(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 19
$\phi$ | 1 | $2\cdot(1\pm{\varepsilon})$ | $\log^{\mathcal{O}(1)}n$ |  [6], Theorem 20
$\phi$ | 2 | $3/2\cdot(1\pm{\varepsilon})$ | $\tilde{\mathcal{O}}(\sqrt{n})$ | Theorem 21

All algorithms can be described as two main steps:

  * •

(Section 4.1) Obtain bounds on $\beta,\gamma,\phi$ in terms of other
structural graph quantities such as number of leaves and number of support
vertices,

  * •

(Section 4.2) Estimate these structural graph quantities in sublinear-space.

###  4.1 Structural Bounds on the Independence Number, Domination number and
Matching number

In this section, we obtain (approximate) upper and lower bounds on the
structural parameters $\beta,\gamma$ and $\phi$ using other structural
parameters of forests. It is well-known that the number of _leaves_ and _non-
leaf vertices_ can be used to approximate some of these graph parameters. For
example, non-leaf vertices are used in $2$-approximating the max matching [6,
18] and $3$-approximating the min domination set in forests [17, 32, 35]. They
are helpful because one can always reason that some min dominating set must be
a subset of them. Similarly, there exists a max independent set that includes
all leaves.

Our main contribution here is to consider the notion of _support vertices_ and
demonstrate their power in approximate the graph parameters $\beta,\gamma$ and
$\phi$. We say that a vertex is a support vertex if it adjacent to at least
one leaf. Each of the graph parameters $\beta,\gamma$ and $\phi$ can be found
in linear space via standard dynamic programming and fixing the subset of
leaves in the solution. Due to our (sublinear) space constraints, we cannot
apply dynamic programming. However, going just one-level above the leaves –
counting the support vertices – is sufficient to improve the approximations.
For any forest $F$, we denote the set of its support vertices by
$\mathit{Supp}(F)$.

####  4.1.1 Structural Bounds on the Independence Number $\beta$

To start, we first show that any tree with at least $3$ vertices has a max
independent set containing every leaf but no support vertex.

######  Lemma 6.

In every tree with $n\geq 3$, there is a maximum independent set containing
all leaves and no support vertices.

###### Proof.

This can be proved via adjusting vertices from a given maximum independent
set. Given a maximum independent set, if it contains all leaves, then we are
done. If some leaves are not included, then their support vertices must be in
the independent set. This can be seen via contradiction, assume that both the
support vertex and its leaves are not in the independent set, then clearly we
could add all the leaves in the set, which violates the assumption that the
set is maximum. Note that each support vertex must be adjacent to at least one
leaf, and if it is in the independent set, none of its leaves is in the set.
Hence, we could remove all support vertices from the given independent set,
and add all their leaves into the set, the size of the resulting set does not
decrease. Given that the original set is already maximum, the new set is also
maximum. ∎

Hence, in the proof of Theorem 10, we assume that the max independent set of
every tree contains every leaf unless $n=2$.

######  Theorem 10.

For every forest $F$ with $n$ vertices, we have

$\max\big{\\{}\,\frac{n}{2}\,,\,\lvert\mathit{Deg}_{1}(F)\rvert-c\big{\\}}\leq\beta(F)\leq\frac{1}{2}\big{(}n+\lvert\mathit{Deg}_{1}(F)\rvert\big{)}\,.$

###### Proof.

To prove Theorem 10, it suffices to show that, for every tree $T$ with
$|T|\geq 2$,

$\max\Big{\\{}\frac{|T|}{2},\lvert\mathit{Deg}_{1}(T)\rvert-1\Big{\\}}\leq\beta(T)\leq\frac{|T|+\lvert\mathit{Deg}_{1}(T)\rvert}{2}\,.$

First we show the lower bound for $\beta(T)$. Since a tree is bipartite and
each side of the bipartition forms an independent set, it follows that
$\beta(T)\geq|T|/2$. Also, when $|T|=2$, $\lvert\mathit{Deg}_{1}(T)\rvert=2$
and $\beta(T)=1$. When $|T|\geq 3$, no two leaves can be adjacent to each
other and hence the set of all leaves forms an independent set, i.e.,
$\beta(T)\geq\lvert\mathit{Deg}_{1}(T)\rvert$. Summarizing, we have
$\beta\geq\max\big{\\{}\frac{|T|}{2},\lvert\mathit{Deg}_{1}(T)\rvert-1\big{\\}}$.

Next, we show that $\beta(T)\leq\frac{|T|+\lvert\mathit{Deg}_{1}(T)\rvert}{2}$
by induction on $|T|$. We say that a pair of leaves of a tree are twins if
they share a common neighbor (support vertex). We have two cases to consider
depending on whether $T$ has twins or not:

##### Case 1: $T$ has twins

Let the twins be $v$, $w$ and their shared neighbor be $u$. Delete $w$, and
let the tree obtained be $T^{\prime}=T-w$. Then we have $|T^{\prime}|=|T|-1$,
$\lvert\mathit{Deg}_{1}(T^{\prime})\rvert=\lvert\mathit{Deg}_{1}(T)\rvert-1$,
and $\beta(T^{\prime})=\beta(T)-1$. By induction hypothesis, we know that

$\displaystyle|T^{\prime}|+|\mathit{Deg}_{1}(T^{\prime})|\geq
2\beta(T^{\prime})$
$\displaystyle\Rightarrow|T|-1)+\big{(}\lvert\mathit{Deg}_{1}(T)\rvert-1\big{)}\geq
2\big{(}\beta(T)-1\big{)}$
$\displaystyle\Rightarrow|T|+\lvert\mathit{Deg}_{1}(T)\rvert\geq 2\beta(T)\,.$

##### Case 2: $T$ does not have twins

Let a leaf $w$ have a parent $u$ whose parent is $x$. We can assume that $u$
has no other leaves adjacent to it since $T$ has no twins. Delete both $u$ and
$w$, and let the obtained tree be $T^{\prime}=T-\\{u,w\\}$. It is easy to see
that $|T^{\prime}|=|T|-2$ and
$\lvert\mathit{Deg}_{1}(T)\rvert\geq\lvert\mathit{Deg}_{1}(T^{\prime})\rvert\geq\lvert\mathit{Deg}_{1}(T)\rvert-1$,
because $x$ may or may not be a leaf in $T^{\prime}$ but $w$ was definitely a
leaf in $T$. Given an independent set $I$ in $T$, we can obtain an independent
set $I^{\prime}=I-w$ in $T^{\prime}$. Similarly, given an independent set
$H^{\prime}$ in $T^{\prime}$, we can obtain an independent set
$H=H^{\prime}\cup\\{w\\}$ in $T$. Hence, it follows that
$\beta(T^{\prime})=\beta(T)-1$. By induction hypothesis, we have

$\displaystyle|T^{\prime}|+\lvert\mathit{Deg}_{1}(T^{\prime})\rvert\geq
2\beta(T^{\prime})$
$\displaystyle\Rightarrow\big{(}|T|-2\big{)}+(\lvert\mathit{Deg}_{1}(T^{\prime})\rvert)\geq
2(\beta(T)-1)$
$\displaystyle\Rightarrow|T|+\lvert\mathit{Deg}_{1}(T)\rvert\geq 2\beta(T)\,.$

∎ Recall that for a forest $F$ we denote its set of leaves by
$\mathit{Deg}_{1}(F)$ and its set of support vertices by $\mathit{Supp}(F)$.

######  Theorem 11.

Let $F$ be a forest with $n$ vertices. Then we have

$\frac{1}{2}\big{(}n+\lvert\mathit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert\big{)}\leq\beta(F)\leq\frac{2}{3}\big{(}n+\lvert\mathit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert\big{)}\,.$

###### Proof.

By Lemma 6, we assume that (unless $n=2$) the maximum independent set contains
every leaf and none of the support vertices. We first show a lower bound
(Proposition 1) and upper bound (Proposition 2) on the independence number of
trees. Theorem 11 then follows immediately by applying Proposition 1 and
Proposition 2 to each tree component of the forest $F$. ∎

######  Proposition 1.

For every tree $T$ with $|T|\geq 2$,

$\beta\geq\frac{1}{2}(|T|+\lvert\mathit{Deg}_{1}(T)\rvert-\lvert\mathit{Supp}(T)\rvert)\,.$

###### Proof.

We prove the proposition by showing that there exists an independent set of
size at least
$\frac{1}{2}\big{(}|T|+\lvert\mathit{Deg}_{1}(T)\rvert-\lvert\mathit{Supp}(T)\rvert\big{)}$.
When $|T|=2$, then $T$ is a path on two vertices which implies $\beta(T)=1$
and $\lvert\mathit{Deg}_{1}\rvert=2=\lvert S\rvert=2$ and the desired
inequality holds. Hence, we assume $n>2$.

It suffices to show that there exists an independent set $H$ containing all
leaves and half of the $\mathit{Deg}_{\geq 2}(T)$ vertices that are not
support vertices. We first remove all leaves and support vertices from $T$ to
obtain a forest $F^{\prime}$ with $\lvert\mathit{Deg}_{\geq
2}(T)\rvert-\lvert\mathit{Supp}(T)\rvert$ vertices. Since each forest is
bipartite and each side of a bipartition forms an independent set, it follows
that $F^{\prime}$ has an independent set $H^{\prime}$ of size
$\geq|F^{\prime}|/2$. We take $H$ to be the union of $\mathit{Deg}_{1}(T)$ and
$H^{\prime}$: it follows that $H$ is an independent set in $T$ since
$F^{\prime}$ does not contain any support vertices of $T$. The size of $H$ is
$|\mathit{Deg}_{1}(T)|+\frac{|\mathit{Deg}_{\geq
2}(T)-\mathit{Supp}(T)|}{2}=\frac{|T|+|\mathit{Deg}_{1}(T)|-\mathit{Supp}(T)}{2}$
since $|T|=|\mathit{Deg}_{1}(T)|+|\mathit{Deg}_{\geq 2}(T)|$. This concludes
the proof of Proposition 1. ∎

The lower bound of Proposition 1 is tight: consider a path $P$ on $2n$
vertices. Then $\beta(P)=n$ and
$\lvert\mathit{Deg}_{1}(P)\rvert=2=\lvert\mathit{Supp}(P)\rvert$.

######  Proposition 2.

For every tree $T$ with $|T|\geq 2$,

$\beta(T)\leq\frac{2}{3}(|T|+\lvert\mathit{Deg}_{1}(T)\rvert-\lvert\mathit{Supp}(T)\rvert)\,.$

###### Proof.

We prove this lemma via induction on the graph order, $n$. Consider all trees
with $2\leq n\leq 4$ as the base cases: these can all be easily verified by
hand. Assume the inequality holds for every tree with order $n-1$. There are
two cases to consider depending on whether $T$ has twins or not:

##### Case 1: There exist twins in $T$

Let $T^{\prime}$ be the tree after removing either one of the twins. Then we
have $|T|=|T^{\prime}|+1$,
$\lvert\mathit{Deg}_{1}(T)\rvert=\lvert\mathit{Deg}_{1}(T^{\prime})\rvert+1$,
and $\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert$.
According to Lemma 6, we have that $\beta(T)=\beta(T^{\prime})+1$. Hence, by
the induction hypothesis, the inequality holds.

##### Case 2: There are no twins in $T$

Consider the longest path in $T$, denote one of its leaves as $x$, the parent
of $x$ as $y$, the parent of $y$ as $w$, and the parent of $w$ as $z$. If $T$
has more than four nodes and no twins, then $z$ is guaranteed to be non-leaf.
This can be seen by contradiction. Assuming $z$ is a leaf and there is more
than four nodes. By our choice of the longest path, the neighbors of $w$ and
$y$ can only be leaves. Since there is no twin, $w$ and $y$ both have degree
two, there are exactly four nodes, a contradiction. By similar argument, it is
not hard to see that $y$ must have degree two.

##### Case 2.1: $d(w)>2$

Remove both $x$ and $y$, and let the resulting tree be $T^{\prime}$. Note that
this removes a leaf and a support vertex. Because $w$ has degree more than 2,
the removal of $x$ and $y$ does not make $w$ a leaf, and $w$ is a support
vertex in $T^{\prime}$ if and only if it is a support vertex in $T$.
Therefore, we have $|T|=|T^{\prime}|+2$,
$\lvert\mathit{Deg}_{1}(T)\rvert=\lvert\mathit{Deg}_{1}(T^{\prime})\rvert+1$,
and $\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert+1$.
Moreover, we claim that $\beta(T)=\beta(T^{\prime})+1$. This is because by
Lemma 6, there is a max independent set $H$ such that $x\in H$ and $y\notin
H$: thus the existence of $x$ and $y$ has no impact on whether $w$ and the
rest of vertices are in $\beta(T)$ or not, i.e., they are in $\beta(T)$ if and
only if they are also in $\beta(T^{\prime})$. By the induction hypothesis, the
inequality holds.

##### Case 2.2: $d(w)=2$

We have two cases to consider.

##### Case 2.2.1: $z\notin\mathit{Supp}(T)$

We remove $x$ and $y$. Similar to Case 2.1, we have $|T|=|T^{\prime}|+2$ and
$\beta(T)=\beta(T^{\prime})+1$. However, since $d(w)=2$ and $z$ is not a
support vertex in $T$, the removal of $x$ and $y$ makes $w$ a leaf and $z$ a
support vertex. Hence
$\lvert\mathit{Deg}_{1}(T)\rvert=\lvert\mathit{Deg}_{1}(T^{\prime})\rvert$,
and $\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert$. By
the induction hypothesis, the inequality holds.

##### Case 2.2.2: $z\in\mathit{Supp}(T)$

Remove $x$, $y$, and $w$ from $T$ and denote the remaining graph as
$T^{\prime}$. Since $z$ is a support vertex, according to Lemma 6, there is a
max indpendent set $H$ of $T$ such that $z\notin H$ which implies that $w$
must in the maximum independent set. Therefore, we have $|T|=|T^{\prime}|+3$
and $\beta(T)=\beta(T^{\prime})+2$. Moreover, removing these vertices make $z$
neither a leaf nor a support vertex in $T^{\prime}$, unless $d(z)=2$. In the
former case, we have
$\lvert\mathit{Deg}_{1}(T)\rvert=\lvert\mathit{Deg}_{1}(T^{\prime})\rvert+1$,
and $\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert+1$. By
the induction hypothesis, the inequality holds. In the latter case, $T$ is a
path of length 5: the claim can easily verified by hand for this specific
graph. This concludes the proof of Proposition 2. ∎

This upper bound of Proposition 2 is asymptotically tight: consider the graph
constructed from a star on $(r+1)$ vertices by replace each of the $r$ leaves
with a path consisting of 3 vertices. Clearly, this graph is a tree, say $T$,
with $3r+1$ vertices, and
$\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Deg}_{1}(T)\rvert=r$. Also,
$\beta(T)=2r$ as all the $r$ leaves and their $r$ grandparents form a maximum
independent set.

Furthermore, combining Theorem 11 with Theorem 10, we have:

######  Corollary 1.

If $\lvert\mathit{Supp}\rvert\leq\frac{1}{2}\,\lvert\mathit{Deg}_{\geq
2}\rvert$,
$\frac{3}{8}\big{(}n+\lvert\mathit{Deg}_{1}\rvert\big{)}\leq\beta\leq\frac{1}{2}\big{(}n+\lvert\mathit{Deg}_{1}\rvert\big{)}\,$.

###### Proof.

By definition, $n=|F|=\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Deg}_{1}(F)\rvert$ and
$\lvert\mathit{Supp}(F)\rvert\leq\lvert\mathit{Deg}_{1}(F)\rvert$. Hence, if
$\lvert\mathit{Supp}(F)\rvert\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{2}$, we have the following inequality,

$\lvert\mathit{Supp}(F)\rvert\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{4}+\frac{\lvert\mathit{Deg}_{1}(F)\rvert}{2}=\frac{n+\lvert\mathit{Deg}_{1}\rvert}{4}\,.$
(6)

Utilizing Equation (6) and combining Theorem 10 and Theorem 11, if
$\lvert\mathit{Supp}(F)\rvert\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{2}$, then

$\frac{3(n+\lvert\mathit{Deg}_{1}(F)\rvert)}{8}\leq\frac{n+\lvert\mathit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert}{2}\leq\beta(F)\,.$

By Theorem 10, we have
$\beta(F)\leq\frac{n+\lvert\mathit{Deg}_{1}(F)\rvert}{2}$ and hence Corollary
1 follows. ∎

####  4.1.2 Structural Bounds on the Domination Number $\gamma$

Many prior works demonstrated that domination number $\gamma$ can be
$3$-approximated using number of non-leaf vertices (vertices with degree at
least two) and number of tree components $c$.

######  Theorem 12.

[17, 35, 32] For every forest $F$ with $c$ components we have

$\frac{1}{3}\,\lvert\mathit{Deg}_{\geq
2}(F)\rvert\leq\gamma(F)\leq\lvert\mathit{Deg}_{\geq 2}(F)\rvert+c\,.$

With the help of support vertices and following a similar approach, we show
that the approximation ratios above can be further improved to $2$.

######  Theorem 13.

For every forest $F$ we have $\frac{1}{4}\big{(}\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert\big{)}\leq\gamma\leq\frac{1}{2}\big{(}\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert\big{)}.$

###### Proof.

By Lemma 7, we will assume that (unless $n<3$) the minimum dominating set
contains all support vertices and no leaves. We first show a upper bound
(Proposition 3) and lower bound (Proposition 4) on the domination number of
trees. Theorem 13 then follows immediately by applying Proposition 3 and
Proposition 4 to each tree component of the forest $F$. ∎

######  Lemma 7.

In every connected graph with $n\geq 3$, there is a minimum dominating set
that contains all support vertices and no leaves.

###### Proof.

We prove this by showing that every minimum dominating set can be adjusted to
contain no leaves and all support vertices without increasing its size.
Clearly, in every connected graph with $n\geq 3$, all support vertices have
degree greater than 1 (i.e., are not themselves leaves). If a support vertex
has degree 1, then its neighbor must be a leaf, hence $n=2$, violating our
assumption about $n\geq 3$. Given a minimum dominating set, If it contains no
leaves and all support vertices, then we are done. If not, we can remove the
leaves from the dominating set and add their neighbors into the set. By the
definition of support vertices, the neighbors of leaves are themselves support
vertices. The resulting set is still a dominating set as the newly added
support vertices dominate the removed leaves and themselves. Moreover, before
the adjustment, for each pair of support vertex and leaf, at least one of them
is in the dominating set, otherwise the domination property is broke. The
adjustment ensures that the new dominating set contains all support vertices
and no leaves. The size of the new dominating set is at most the size of
original dominating set, because each removed leaf introduces at most one
neighbor (i.e., support vertex) into the new set. ∎

Hence, in the following section, we assume the minimum dominating set contains
all support vertices and no leaves. Now we give our upper and lower bounds on
the domination number of forest. For the upper bound, we have

######  Proposition 3.

For every forest $F$, we have

$\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}\geq\gamma(F)\,.$

###### Proof.

If $|F|=2$, then $F$ has to be an edge. Every vertex of $F$ is both a support
vertex and a leaf, and we can pick either of them as the dominating set.
Hence,

$\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}=\frac{1+1}{2}=1=\gamma(F)\,,$

the inequality holds.

Next, we prove the inequality for graphs with $n>2$. It is known that if a
graph $G$ is split into $k$ disjoint subgraphs, $G_{1},G_{2},\dots,G_{k}$, we
have $\gamma(G)\leq\gamma(G_{1})+\gamma(G_{2})+\dots+\gamma(G_{k})$. This is
because connecting two or more disjoint graphs only introduces new edges, thus
vertices do not become undominated. Rewriting the inequality LHS as

$\lvert\mathit{Supp}(F)\rvert+\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert-\lvert\mathit{Supp}(F)\rvert}{2}\,,$

the first term could be viewed as adding all vertices in $\mathit{Supp}(F)$
into the dominating set. By doing so, all of the vertices in
$N\big{[}\mathit{Supp}(F)\big{]}$ are dominated (note that this includes all
the leaves). The second term could be viewed as an upper bound on the
domination number after removing all the leaves and support vertices. Clearly,
the remaining graph is a forest with $(\lvert\mathit{Deg}_{\geq
2}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)$ vertices. Thus it remains to prove
that in such a forest, there exists a dominating set of size at most
$(\lvert\mathit{Deg}_{\geq 2}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)/{2}$.

Note that all isolated vertices in the induced graph are already dominated by
some vertices in $S$, because a vertex becomes isolated only if all of its
neighbors are in $S$. Thus, we only need to show that for each tree components
(of size $k>1$) in the remaining forest, there exists a dominating set of size
at most ${k}/{2}$. Ore [39] proved that for every graph $G$ with order $n$ and
no isolated vertices, $\gamma(G)\leq{n}/{2}$. Hence, this proposition follows.
∎

The upper bound of Proposition 3 is tight: construct a tree $T$ by taking a
path of on $r$ vertices for any $r\geq 2$, add a leaf to every vertex on the
path. It is easy to see that $|\mathit{Supp}(T)|=|\mathit{Deg}_{\geq
2}(T)|=\gamma(T)=r$.

Next, we present our lower bound result.

######  Proposition 4.

For every tree $T$ with $T|\geq 2$,

$\gamma(T)\geq\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert}{4}\,.$

###### Proof.

We prove the proposition by induction on $n=|T|$. Consider the base cases as
trees with $n\leq 4$, which can be easily verified by hand.

It remains to show the inductive step. Two or more leaves are twins if they
share a common parent node (i.e., support vertex). If the tree contains twins,
we remove any one of them from $T$ to obtain a tree $T^{\prime}$. By Lemma 7,
the minimum dominating set of $T$ does not contain either of the twins. Hence,
we have that $\gamma(T)=\gamma(T^{\prime})$, $\lvert\mathit{Deg}_{\geq
2}(T)\rvert=|\mathit{Deg}_{\geq 2}(T^{\prime})|$, and
$\lvert\mathit{Supp}(T)=\mathit{Supp}(T^{\prime})\rvert$ stay the same. By
induction hypothesis, Proposition 4 holds.

Next, assume there are no twins and consider the longest path, say $P$, in
$T$. Denote the two endpoints as $x$ and $x^{\prime}$ respectively, let $y$ be
the parent of $x$, $w$ be the parent of $y$, and $z$ be the parent of $w$.
Note that the length of $P$ must be greater than 4, thus $z$ and $x^{\prime}$
must be different. This can be seen via contradiction. Assuming $P$ has length
$4$, by our choice of longest path $P$, $x$ and $z$ (or equivalently,
$x^{\prime}$) must be leaves, and the neighbors of $y$ and $w$ must be also
leaves. Otherwise, our choice of the longest path is violated. If $y$ or $w$
is adjacent to leaves other than $x$ and $z$, then there exist twins in the
graph, violating our assumption of no twins. Hence, the graph contains exactly
4 vertices, $x$, $y$, $w$, and $z$. It should be considered as the base case.
Similar arguments can be obtained for $P$ with length less than $4$. Hence,
$P$’s length must be greater than 4.

If $w$ is a support vertex, then we are done by induction. By Lemma 7, the
minimum dominating set contains both $w$ and $y$ as they are support vertices.
Note that $y$ must have degree exactly 2, otherwise the graph has either a
twin, or a path longer than $P$. Delete $x$ and let the tree obtained be
$T^{\prime\prime}$. Then $y$ becomes a leaf which is already dominated by $w$.
Therefore, after removing $x$, we have $\gamma(T^{\prime\prime})=\gamma(T)-1$.
Since $y$ becomes a leaf, we have $|\mathit{Deg}_{\geq
2}(T^{\prime\prime})|=|\mathit{Deg}_{\geq 2}(T)|-1$ and
$|\mathit{Supp}(T^{\prime\prime})|=|\mathit{Supp}(T)|-1$, and hence the
inequality holds by our induction hypothesis.

It remains to show that $\gamma(T)\geq(\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert)/{4}$ when there are no twins and $w$
is not a support vertex. Let $T^{\prime}$ and $T^{\prime\prime}$ be the two
sub-trees formed by deleting the edge $(w,z)$, such that $T^{\prime}$ contains
$w$ and $T^{\prime\prime}$ contains $z$. Note that by our previous analysis,
only paths of length 2 can be incident on $w$, otherwise the tree falls into
previous cases. Denote the number of such paths as $r$; clearly, $r\geq 1$
because there is path from $x$ to $w$. In tree $T^{\prime}$, clearly, by
picking all $r$ child nodes of $w$, we obtain a minimum dominating set. Since
$w$ is not included in the set,
$\gamma(T)=\gamma(T^{\prime})+\gamma(T^{\prime\prime})=r+\gamma(T^{\prime\prime})$.
Let $\psi(T)=\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert$. We have the following three
inequalities:

  1. 1.

if $d(z)>1$ in $T^{\prime\prime}$: $\mathit{Deg}_{\geq
2}(T)\leq\mathit{Deg}_{\geq 2}(T^{\prime\prime})+(r+1)$.

  2. 2.

if $d(z)=1$ in $T^{\prime\prime}$: $\mathit{Deg}_{\geq
2}(T)\leq\mathit{Deg}_{\geq 2}(T^{\prime\prime})+(r+1)+1$.

  3. 3.

$\mathit{Supp}(T)\leq\mathit{Supp}(T^{\prime\prime})+r$.

The first two inequalities hold because $T^{\prime}$ contains $r$ vertices
from $\mathit{Deg}_{\geq 2}(T^{\prime})$ vertices, and by adding the edge
$(w,z)$ we have $d(w)\geq 2$. Also, if $z$ has degree 1 in $T^{\prime\prime}$,
$z$ is not in $\mathit{Deg}_{\geq 2}(T^{\prime\prime})$, but adding the edge
$(w,z)$ puts it in $\mathit{Deg}_{\geq 2}(T)$. Otherwise, $z$ is already in
$\mathit{Deg}_{\geq 2}(T^{\prime\prime})$. Similarly, the _third_ inequality
holds because there are $r$ vertices in $\mathit{Supp}(T^{\prime})$, adding
the edge $(w,z)$ does not introduce new support vertices in
$\mathit{Supp}(T)$. Hence,
$\mathit{Supp}(T)\leq\mathit{Supp}(T^{\prime\prime})+r$. This is an inequality
because adding the edge $(w,z)$ makes $z$ non-leaf, thus a support vertex
might be removed. Therefore, we have $\psi(T)\leq\psi(T^{\prime\prime})+2r+2$.
And:

$\displaystyle\gamma(T)$ $\displaystyle=\gamma(T^{\prime\prime})+r$
$\displaystyle\geq\frac{\lvert\mathit{Deg}_{\geq
2}(T^{\prime\prime})\rvert+\lvert\mathit{Supp}(T^{\prime\prime})\rvert}{4}+r\,\,\,\quad\textnormal{[by
induction hypothesis]}$ $\displaystyle=\frac{\lvert\mathit{Deg}_{\geq
2}(T^{\prime\prime})\rvert+\lvert\mathit{Supp}(T^{\prime\prime})\rvert+4r}{4}$
$\displaystyle\geq\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert}{4}\,,$

where the last inequality holds because $4r\geq 2r+2$ when $r\geq 1$, which is
always true since there is a path from $w$ to $x$. ∎

The lower bound in Proposition 4 is asymptotically tight. Consider the tree
$T$ containing a vertex $v$ with one leaf and $r$ paths of length 4 ($P_{4}$)
incident on it, which can be also viewed as a star graph with $r+1$ leaves
except $r$ of them are replaced with $P_{4}$. Clearly, we have
$\gamma(T)=r+1$. Meanwhile, we have $|\mathit{Deg}_{\geq 2}(T)|=3r+1$, and
$\lvert\mathit{Supp}(T)\rvert=r+1$. Hence,

$\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert}{4}=\frac{4r+2}{4}\approx
r+\frac{1}{2}\,.$

When $r\rightarrow\infty$, the ratio of ${r+1}$ to $r+\frac{1}{2}$ limits to
$1$.

Combining Proposition 3 and Proposition 4, we have Theorem 13. Moreover,
combining Theorem 13 and Theorem 12, if
$\lvert\mathit{Supp}(F)\rvert\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{3}$, we have

$\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{3}\leq\gamma(F)\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}\leq\frac{2\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{3}\,,$

whence Corollary 2 follows.

######  Corollary 2.

If $\lvert\mathit{Supp}\rvert\leq\frac{1}{3}\,\lvert\mathit{Deg}_{\geq
2}\rvert$, then $\frac{1}{3}\,\lvert\mathit{Deg}_{\geq
2}\rvert\leq\gamma\leq\frac{2}{3}\,\lvert\mathit{Deg}_{\geq 2}\rvert\,$.

####  4.1.3 Structural Bounds on the Matching Number $\phi$

Similarly, previous works showed that matching number, $\phi$, can be
$2$-approximated.

######  Theorem 14.

[6, 18] For every forest $F$,
$\max\big{\\{}\,c\,,\,\frac{1}{2}(\lvert\mathit{Deg}_{\geq 2}\rvert+c)\
\big{\\}}\leq\phi\leq\lvert\mathit{Deg}_{\geq 2}\rvert+c\,$.

We then show that the approximation ratios above can be further improved to
$3/2$ using support vertices.

######  Theorem 15.

For every forest $F$, $\frac{1}{3}\big{(}\lvert\mathit{Deg}_{\geq
2}\rvert+\lvert\mathit{Supp}\rvert\big{)}\leq\phi\leq\frac{1}{2}\big{(}\lvert\mathit{Deg}_{\geq
2}\rvert+\lvert\mathit{Supp}\rvert\big{)}\,$.

###### Proof.

By Lemma 8, we will assume that (unless $n<2$) every support vertex is matched
via at least one edge in the maximum matching. We first show a upper bound
(Proposition 5) and lower bound (Proposition 6) on the matching number of
trees. Theorem 15 then follows immediately by applying both propositions to
each tree component of the forest $F$. ∎

######  Lemma 8.

In every connected graph with $n\geq 3$, there is a maximum matching such that
every support vertex is matched by one of its edges between it and its leaves.

###### Proof.

The first half of the lemma (every support vertex is matched) can be proved
via contradiction. Assume we have a maximum matching and a support vertex $s$
is not matched, then we could include an edge between $s$ and one of its
leaves into the matching, a contradiction.

The latter half can be proved via alternating edges in every given maximum
matching without decreasing its size. Given a maximum matching $M$. If $M$
satisfies the condition, then we are done. If there is a support vertex $s$
that is matched through an edge between it and a non-leaf vertex, then by the
definition of matching, none of its leaves are matched. Hence, we can remove
the matching edge of $s$ and include one of the edges between $s$ and its
leaves into the matching. This is valid as the leaf is not matched before, and
$s$ is matched only by the newly added edge. The size of maximum matching does
not decrease. ∎

We may now prove an upper bound on $\phi$.

######  Proposition 5.

For every tree $T$ with $n\geq 2$,

$\phi\leq\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert}{2}\,.$

###### Proof.

We prove the proposition by induction on $n=|T|$. If $|T|=2$, then $T$ is an
edge and we have $\phi(T)=1,\lvert\mathit{Deg}_{\geq 2}(T)\rvert=0$ and
$\lvert S\rvert=2$: hence the inequality holds. Henceforth, we assume that
$n>2$. Rearranging the upper bound, we have

$\lvert\mathit{Supp}(T)\rvert+\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert-\lvert\mathit{Supp}(T)\rvert}{2}\,.$

By Lemma 8, all support vertices are matched by the edges between them and one
of their leaves. Hence, removing all support vertices and their leaves removes
$\lvert S\rvert$ edges in the matching. The remaining graph is a forest $F$
with $n(F)=\lvert\mathit{Deg}_{\geq 2}(T)\rvert-\lvert S\rvert$, and all edges
in $F$ can be added into the matching as they do not share a common endpoint
with edges between support vertices and leaves (i.e., the matching edges that
are removed). Hence it remains to prove that for every forest, there is a
matching of size at most $\frac{n(F)}{2}$. Since every forest is bipartite,
and in a bipartite graph with total order of $n$, the matching number is at
most $\frac{n}{2}$. This is because one side has at most $\frac{n}{2}$ nodes.
By the Pigeonhole Principle, if there is a matching of size greater than
$\frac{n}{2}$, at least one node has more than one matching edges incident on
it, a contradiction. ∎

The upper bound of Proposition 5 is tight: consider the tree $T$ obtained by
taking a star graph $H$ with $r$ leaves and attaching a new leaf for each
vertex in $H$ (including the center). It is easy to see that
$\lvert\mathit{Deg}_{\geq 2}(T)\rvert=\lvert\mathit{Supp}(T)\rvert=r+1$, as
all vertices in $H$ become a support vertex and have more than 1 neighbor. And
it is not hard to see that $\phi=r+1$, as the maximum matching is the edge set
$E(T)\setminus E(H)$.

The next proposition gives a lower bound for the matching number:

######  Proposition 6.

For every tree $T$ with $|T|\geq 2$,

$\phi(T)\geq\frac{\lvert\mathit{Deg}_{\geq
2}(T)\rvert+\lvert\mathit{Supp}(T)\rvert}{3}\,.$

###### Proof.

We prove the proposition by induction on $n=|T|$. We consider trees with
$2\leq n\leq 4$ as the base cases, which can be easily verified by hand. There
are two cases to consider depending on whether not $T$ contains twins.

##### Case 1: There exist twins in $T$

Let $x,y$ be the leaves which are twins and let $s$ be the common vertex that
they are adjacent to. Remove either of $x$ or $y$, and let $T^{\prime}$ be the
tree after the removal. Note that in $T^{\prime}$, $s$ is a leaf if and only
if $d(s)=2$ in $T$, in this case $n=3$, which falls into our base case. Hence,
we have $\lvert\mathit{Deg}_{\geq 2}(T)\rvert=\mathit{Deg}_{\geq
2}(T^{\prime})$ and
$\lvert\mathit{Supp}(T)\rvert=|\mathit{Supp}(T^{\prime})|$. Moreover, we claim
that $\phi(T)=\phi(T^{\prime})$: this is because only one of $s$’s edges can
be included into matching, if the removed leaf is on this edge, then we could
add another edge between $s$ and the other one of twin. By the induction
hypothesis, this inequality holds.

##### Case 2: There are no twins in $T$

Consider the longest path in $T$, denote one of its endpoint as $x$, the
parent of $x$ as $y$, the parent of $y$ as $w$, and the parent of $w$ as $z$.
By the induction hypothesis, $T$ has more than 4 nodes and no twins, hence $z$
is guaranteed to be a non-leaf. This can be seen by contradiction. Assuming
$z$ is leaf, by our choice of longest path, the neighbors of $w$ and $y$ can
only be leaves. Otherwise, there exists a longer path. Also, since there is no
twin, $w$ and $y$ both have degree 2, thus there is exactly 4 nodes, a
contradiction. By similar argument, it is not hard to see that $y$ is
guaranteed to have degree 2.

##### Case 2.1: $d(w)>2$

We remove both $x$ and $y$, denote the resulting tree as $T^{\prime}$. Since
$d(w)>2$, removing $x$ and $y$ does not make $w$ leaf, thus
$\lvert\mathit{Deg}_{\geq 2}(T)\rvert=\lvert\mathit{Deg}_{\geq
2}(T^{\prime})\rvert+1$. Also, $w$ is a support vertex in $T^{\prime}$ if and
only if it is a support vertex in $T$, we have
$\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert+1$. By
Lemma 8, we know that $e(x,y)$ is in the maximum matching of $T$, but not
$e(y,w)$. Hence, the removal of $x$ and $y$ does not change the matching
status of vertices in $T^{\prime}$: this implies that
$\phi(T)=\phi(T^{\prime})+1$. By the induction hypothesis, the inequality
holds.

##### Case 2.2: $d(w)=2$

We have two cases to consider:

##### Case 2.2.1: $z\notin\mathit{Supp}(T)$

We remove $x$ and $y$. Similar to Case 2.1, we have
$\phi(T)=\phi(T^{\prime})+1$. However, since $d_{w}=2$ and $z$ is not a
support vertex in $T$, the removal of $x$ and $y$ makes $w$ a leaf and $z$ a
support vertex. Hence $\lvert\mathit{Deg}_{\geq
2}(T)\rvert=\lvert\mathit{Deg}_{\geq 2}(T^{\prime})\rvert+2$, and
$\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert$. By the
induction hypothesis, the inequality holds.

##### Case 2.2.2: $z\in\mathit{Supp}(T)$

Consider $T^{\prime}$ as the tree after removing $x$, $y$, and $w$ from $T$.
Since $z$ is a support vertex, according to Lemma 8, $z$ must be matched and
$e(x,y)$ is in the maximum matching. Hence, we know that $e(y,w)$ and $e(w,z)$
are not in the matching, and the removal of $x$, $y$, and $w$ does not change
the matching status of vertices in $T^{\prime}$. Therefore,
$\phi(T)=\phi(T^{\prime})+1$. Moreover, removing these three vertices does not
make $z$ a leaf or make it not a support vertex in $T^{\prime}$, unless $z$
itself has degree 2. In the former case, we have $\lvert\mathit{Deg}_{\geq
2}(T)\rvert=\lvert\mathit{Deg}_{\geq 2}(T^{\prime})\rvert+2$, and
$\lvert\mathit{Supp}(T)\rvert=\lvert\mathit{Supp}(T^{\prime})\rvert+1$. And by
the induction hypothesis, the inequality holds. In the later case, we have a
path on $5$ veryices since $x$ is a leaf, $y$, $w$, and $z$ have degree 2, and
$z$ is also a support vertex. It can be easily verified by hand that the
inequality holds for $P5$. ∎

The lower bound is asymptotically tight. Consider a graph $G$ constructed as
follows. Start with a star graph, $H$, with $r$ leaves, and replace each leaf
with a path of length $3$. $G$ has $2r+1$ non-leaf vertices, including the
star center and two of the vertices on each of the paths. Also
$\lvert\mathit{Supp}(G)\rvert=r$ as only the middle vertices on the paths are
support vertices. Lastly, a maximum matching can be found by adding all edges
between support vertices and leaves, and one edge from the edges incident on
star center, thus $\phi(G)=r+1$.

Theorem 15 follows if we combine Proposition 5 and Proposition 6. Moreover,
combining Theorem 14 and Theorem 15, if
$\lvert\mathit{Supp}(F)\rvert\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}{3}$, we have:

$\phi(F)\leq\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}\leq\frac{3(\lvert\mathit{Deg}_{\geq
2}(F)\rvert+c(F))}{4}\,.$

Since, by Theorem 14, $\phi(F)\geq\max\\{c(F),\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+c(F)}{2}\\}$, Corollary 3 follows.

######  Corollary 3.

If $\lvert\mathit{Supp}\rvert\leq\frac{1}{2}\,\lvert\mathit{Deg}_{\geq
2}\rvert$, then $\max\big{\\{}c,\frac{\lvert\mathit{Deg}_{\geq
2}\rvert+c}{2}\big{\\}}\leq\phi\leq\frac{3}{4}\cdot\big{(}\lvert\mathit{Deg}_{\geq
2}\rvert+c\big{)}\,$.

###  4.2 One-pass and Two-pass Sublinear Streaming Algorithms for Estimating
the Independence Number, Domination number and Matching number

In Section 4.1 we obtained (approximate) upper and lower bounds for
$\beta,\gamma$ and $\phi$ in terms of other forest parameters such as number
of leaves, number of non-leaves, number of support vertices, etc. Now we
estimate these latter quantities in sublinear space to obtain one-pass and
two-pass streaming algorithms which estimate $\beta,\gamma$ and $\phi$.

####  4.2.1 One-pass and Two-pass Streaming Algorithms for Estimating $\beta$

We show how to estimate the structural graph quantities within factor
$(1\pm{\varepsilon})$, in small space. Our algorithms rely on the concept of
the degree vector $\mathcal{D}(F)$: the $i^{\text{th}}$ coordinate holds the
degree of vertex $i$. Storing this vector would require $\Theta(n\log n)$
bits, exceeding our working-space bound. Hence we rely on sparse-recovery
techniques to estimate quantities that are functions of $\mathcal{D}(F)$,
supporting fast stream updates.

##### Estimating Non-leaf Vertices

Though $\beta$ estimation does not use $\lvert\mathit{Deg}_{\geq 2}\rvert$, it
helps to estimate $\gamma$ and $\phi$. Consider the vector
$\mathcal{D}^{\prime}(F)=\mathcal{D}(F)+\\{-1\\}^{n}$. Since we assume $F$ has
no isolated vertices, the number of non-zero entries in
$\mathcal{D}^{\prime}(F)$ is the number of vertices of degree at least $2$,
viz. $\|\mathcal{D}^{\prime}(F)\|_{0}=\lvert\mathit{Deg}_{\geq 2}\rvert$.
Applying Theorem 2, we $(1\pm{\varepsilon})$-approximate
$\lvert\mathit{Deg}_{\geq 2}\rvert$ in $\log^{\mathcal{O}(1)}n$ space with
constant success probability. Since no existing $L_{0}$ sketch supports
initialization with $\\{-1\\}^{n}$, degree decrements are post-processed.
Running $\mathcal{O}(\log\delta^{-1})$ independent instances and returning the
median, the failure probability is less than $\delta$.

######  Lemma 9.

Given ${\varepsilon},\delta\in(0,1)$, $\lvert\mathit{Deg}_{\geq 2}\rvert$ is
$(1\pm{\varepsilon})$-approximated in a turnstile stream with probability
$(1-\delta)$ and in $\mathcal{O}(\log^{\mathcal{O}(1)}n\cdot\log\delta^{-1})$
space.

##### Estimating Leaves

We can estimate $\lvert\mathit{Deg}_{1}\rvert$ with
$n-\lvert\mathit{Deg}_{\geq 2}\rvert$. But if $\lvert\mathit{Deg}_{1}\rvert$
is in $o(\lvert\mathit{Deg}_{\geq 2}\rvert)$, the relative error can be very
large. We turn elsewhere.

######  Lemma 10.

For every forest,
$\lvert\mathit{Deg}_{1}\rvert=2c+\sum^{\Delta}_{i=3}(i-2)\cdot\lvert\mathit{Deg}_{i}\rvert\,$.

###### Proof.

We prove this lemma by showing the following proposition:

######  Proposition 7.

For each tree $T$ (with at least two vertices) we have
$\lvert\mathit{Deg}_{1}(T)\rvert=2+\sum^{\Delta}_{i=3}(i-2)\cdot\lvert\mathit{Deg}_{i}(T)\rvert$.

###### Proof.

$\displaystyle\sum^{\Delta}_{i=3}(i-2)\cdot\lvert\mathit{Deg}_{i}(T)\rvert=\sum^{\Delta}_{i=2}(i-2)\cdot\lvert\mathit{Deg}_{i}(T)\rvert$
$\displaystyle=\sum^{\Delta}_{i=2}i\cdot\lvert\mathit{Deg}_{i}(T)\rvert-2\cdot\sum^{\Delta}_{i=2}\lvert\mathit{Deg}_{i}(T)\rvert$
$\displaystyle=\Big{(}(2|T|-2)-\mathit{Deg}_{1}(T)\Big{)}-2\cdot\Big{(}|T|-\mathit{Deg}_{1}(T)\Big{)}$
$\displaystyle=\mathit{Deg}_{1}(T)-2\,.$

In the penultimate line, we have used the fact that $\sum_{v\in
T}d(v)=2|T|-2$. ∎

The proof of Lemma 10 then follows from Proposition 7 by summing up over all
tree components of $F$. ∎

Post-processing $\mathcal{D}$ with $\\{-2\\}^{n}$, to obtain
$\mathcal{D}^{\prime\prime}$, we have
$\|\mathcal{D}^{\prime\prime}(F)\|_{1}=\lvert\mathit{Deg}_{1}\rvert+\sum_{i=3}^{\Delta}(i-2)\cdot\lvert\mathit{Deg}_{i}\rvert\,$.
Folding in Lemma 10, we have
$\lvert\mathit{Deg}_{1}\rvert=\|\mathcal{D}^{\prime\prime}(F)\|_{1}/{2}+c$, so
via Theorem 1 we have

######  Lemma 11.

Given ${\varepsilon},\delta\in(0,1)$, $\lvert\textit{Deg}_{1}\rvert$ is
$(1\pm{\varepsilon})$-approximated in a turnstile stream with probability
$(1-\delta)$ in $\mathcal{O}(\log^{\mathcal{O}(1)}n\cdot\log\delta^{-1})$
space.

Combining Lemma 11 with Theorem 10, we conclude:

######  Theorem 16.

Forest independence number $\beta$ is
$3/2\cdot(1\pm{\varepsilon})$-approximated with probability $(1-\delta)$ on
turnstile streams using
$\mathcal{O}(\log^{\mathcal{O}(1)}n\cdot\log\delta^{-1})$ space.

##### Estimating Support Vertices

Degree-counting, above, does not suffice to estimate the number of support
vertices. We first show, in Subroutine 3, given a turnstile streamed forest,
how to output an $(1\pm{\varepsilon})$-estimate of
$\lvert\mathit{Supp}\rvert$, when $\lvert\mathit{Supp}\rvert$ is at least a
threshold $K_{1}$. When $\lvert\mathit{Supp}(F)\rvert$ is small, we can
approximate $\beta$ via either of the following methods:

  * •

If few non-leaves, find $|\mathit{Deg}_{\geq 2}\rvert$ and
$\lvert\mathit{Supp}(F)\rvert$ exactly (Subroutine 4).

  * •

If many non-leaves, Corollary 1 enables excluding
$\lvert\mathit{Supp}(F)\rvert$.

Similar to Cormode et al. [12] and to Jayaram and Woodruff [26], we assume the
number of deletions is $\mathcal{O}(n)$, preserving the analyses of
Subroutines 3 and 4.

Subroutine 3 Estimating $\lvert\mathit{Supp}\rvert$

1:Input: Size threshold $K_{1}$, constant $c_{1}$, and error rate
${\varepsilon}_{1}\in(0,1)$

2:Initialization: $I\leftarrow\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}$
vertices sampled uniformly at random from $[n]$

3:for $v\in I$ do

4: $l(v)\leftarrow\\{\\}$

5:$m,t\leftarrow 0$

6:First Pass:

7:for all $(e=(u,v),i)$ in the stream, with $i\in\pm 1$ do

8: $m\leftarrow m+i$

9: if $u\in I$ then

10: Toggle $v$’s presence in $l(u)$

11: $t\leftarrow t+i$

12: Perform the same operation on $v$

13: Abort if
$t\geq\frac{2m}{n}\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}e^{\frac{c_{1}}{3}}$

14:Second Pass:

15:Count the degree of every vertex in $I\cup\left(\bigcup_{w\in
I}\,l(w)\right)$

16:$C\leftarrow\\{u\mid u\in I\text{ and there is some leaf $v\in l(u)$\\}}$

17:return $\widehat{\lvert\mathit{Supp}(F)\rvert}\leftarrow\lvert
C\rvert\times\frac{{\varepsilon}_{1}^{2}K_{1}}{c_{1}}$

######  Lemma 12.

Given threshold $K_{1}$, constant $c_{1}$, and error rate
${\varepsilon}_{1}\in(0,1)$, Subroutine 3 is a turnstile-stream algorithm that
uses $\widetilde{\mathcal{O}}({n}/({\varepsilon}_{1}^{2}K_{1}))$ space and:
when $\lvert\mathit{Supp}(F)\rvert\geq K_{1}$,
$(1\pm{\varepsilon}_{1})$-approximates $\lvert\mathit{Supp}(F)\rvert$ with
probability $\geq 1-3e^{-\frac{c_{1}}{3}}$; when
$\lvert\mathit{Supp}(F)\rvert<K_{1}$, returns an estimate at most $2K_{1}$
with probability $\geq 1-2e^{-\frac{c_{1}}{3}}$.

###### Proof.

We claim that, conditional on the algorithm does not abort at line 13, the
candidate set, $C$, obtained at line 16 contains only vertices from
$\mathit{Supp}(F)$, and if a vertex in $\mathit{Supp}(F)$ is sampled, it is
kept in $C$. This is not hard to see, by performing a second pass, we obtain
the exact degree of all sampled vertices and their neighbors. So that a vertex
is included in $C$ if there is at least one leaf adjacent to it, which is
exactly the definition of $\mathit{Supp}(F)$.

It remains to bound the output of this algorithm, conditional on the algorithm
does not abort. For all $i\in V(G)$, let the binary random variable $X_{i}$
indicate whether a vertex $v_{i}$ is a support vertex and is sampled in $I$.
Let $X=\sum_{i\in G}X_{i}$. Clearly, since vertices are sampled uniformly with
probability $p=\frac{c_{1}}{{\varepsilon}_{1}^{2}K_{1}}$, we have

$\displaystyle E[X]$ $\displaystyle=\sum_{i\in G}E[X_{i}]=\sum_{i\in
G}\Pr[v_{i}\in(\mathit{Supp}(F)\cap I)]$
$\displaystyle=\sum_{i\in\mathit{Supp}(F)}\Pr[v_{i}\in
I]=\frac{c_{1}\,\lvert\mathit{Supp}(F)\rvert}{{\varepsilon}_{1}^{2}K_{1}}\,.$

Thus
$E[\lvert\widehat{S}\rvert]=\frac{{\varepsilon}_{1}^{2}K_{1}}{c_{1}}\times
E[X]=\lvert\mathit{Supp}(F)\rvert$. Moreover, when
$\lvert\mathit{Supp}(F)\rvert\geq K_{1}$, we have

$\displaystyle\Pr\big{[}\big{\lvert}\lvert\widehat{S}\rvert-\lvert\mathit{Supp}(F)\rvert\big{\rvert}\geq{\varepsilon}_{1}\lvert\mathit{Supp}(F)\rvert\big{]}$
$\displaystyle=\Pr\big{[}\lvert X-E[X]\rvert\geq{\varepsilon}_{1}E[X]\big{]}$
$\displaystyle\leq 2e^{-\frac{{\varepsilon}_{1}^{2}E[X]}{3}}$
$\displaystyle\leq 2e^{-c_{1}/3}\,,$

where we apply the negatively correlated Chernoff bound (Theorem 5) in the
second-last inequality, since the $X_{i}$’s are negatively correlated. And the
last inequality holds as $\lvert\mathit{Supp}(F)\rvert\geq K_{1}$.

Next, we show that when $\lvert\mathit{Supp}(F)\rvert<K_{1}$, conditional on
the algorithm does not abort, the probability that $\lvert\widehat{S}\rvert$
is larger than $2K_{1}$ is small. Again, by the negatively correlated Chernoff
bound, we have

$\displaystyle\Pr\big{[}\lvert\widehat{S}\rvert>2K_{1}\big{]}$
$\displaystyle=\Pr\big{[}X>\frac{2K_{1}E[X]}{\lvert\mathit{Supp}(F)\rvert}\big{]}$
$\displaystyle<\Pr\big{[}X>(1+\frac{K_{1}}{\lvert\mathit{Supp}(F)\rvert})E[X]\big{]}$
$\displaystyle\leq
e^{-\frac{K_{1}^{2}E[X]}{3\lvert\mathit{Supp}(F)\rvert^{2}}}$
$\displaystyle\leq
e^{-\frac{c_{1}K_{1}}{3\lvert\mathit{Supp}(F)\rvert{\varepsilon}^{2}}}$
$\displaystyle\leq e^{-\frac{c_{1}}{3{\varepsilon}^{2}}}\,,$

where the first and the last inequalities hold because
$\lvert\mathit{Supp}(F)\rvert<K_{1}$.

Lastly, we bound the space usage of the algorithm and the probability that the
algorithm aborts at line 13. By the design of the algorithm, at most
$\frac{2m}{n}\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}e^{\frac{c_{1}}{3}}~{}$
vertices can be stored from the first pass, otherwise it aborts at line 13. By
our assumption, the number of total edge insertions is bounded by
$\mathcal{O}(n)$. Thus, we have $\frac{2m}{n}\in\mathcal{O}(1)$. Therefore,
since each vertex requires $\mathcal{O}(\log n)$ bits to store its identifier,
the space usage of the first pass is
$\widetilde{\mathcal{O}}(\frac{n}{{\varepsilon}_{1}^{2}K_{1}})$. Moreover, in
the second pass, each degree counter takes an additional $\mathcal{O}(\log n)$
space to store. Hence, the total space usage is still
$\widetilde{\mathcal{O}}(\frac{n}{{\varepsilon}_{1}^{2}K_{1}})$.

In this algorithm, we sampled $\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}$
vertices in advance. And the average degree of the graph at any point of the
stream can be calculated as $\frac{2m}{n}$. Hence, if we pick a vertex
uniformly at random, the expected number of its neighbors is bounded by
$\frac{2m}{n}$. Let $Y_{i}$ be the number of neighbors of vertex $i$,
$E[Y_{i}]=\frac{2m}{n}$. Let $Y=\sum_{v\in V(G)}Y_{v}$ We have

$E[Y]=\sum_{v\in
V(G)}E[Y_{v}]=\frac{2m}{n}\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}\,.$

The algorithm aborts if more than
$\frac{2m}{n}\frac{c_{1}n}{{\varepsilon}_{1}^{2}K_{1}}e^{\frac{c_{1}}{3}}$
vertices are retained. Since we are sampling each vertex uniformly at random,
$Y_{v}$’s are independent of each other. By Markov inequality, the probability
that the actual size is $e^{\frac{c_{1}}{3}}$ times larger than the expected
size is at most $e^{-\frac{c_{1}}{3}}$.

Applying a union bound with the abort probability and the concentration
probabilities above, we can bound the fail probability of our algorithm as
follows. When $\lvert\mathit{Supp}(F)\rvert~{}\geq~{}K_{1}$, Algorithm 3
outputs an $(1\pm{\varepsilon})$-estimate of $\lvert\mathit{Supp}(F)\rvert$
and fails with probability at most
$2e^{-\frac{c_{1}}{3}}+e^{-\frac{c_{1}}{3}}=3e^{-\frac{c_{1}}{3}}$. Similarly,
when $\lvert\mathit{Supp}(F)\rvert<K_{1}$, the estimate returned by Algorithm
3 is larger than $2K_{1}$ with probability at most
$e^{-\frac{c_{1}}{3{\varepsilon}_{1}^{2}}}+e^{-\frac{c_{1}}{3}}<2e^{-\frac{c_{1}}{3}}$
since ${\varepsilon}_{1}<1$. ∎

Sparse recovery on $\mathcal{D}^{\prime}$ recovers all vertices in
$\mathit{Deg}_{\geq 2}$, with probability $1-\delta$, but no leaves. In a
second pass, we verify whether each recovered vertex is a support vertex. For
a length-two path (a $P_{2}$, i.e., an isolated edge), neither endpoint is
recovered. Except in the case of a $P_{2}$ path, if some neighbour of vertex
$u$ is not recovered, then $u$ is a support vertex. Since no leaf is
recovered, Subroutine 4 shows how to verify $\mathit{Deg}_{\geq 2}$.

Subroutine 4 Estimating $\lvert\mathit{Supp}(F)\rvert$ when
$\lvert\mathit{Deg}_{\geq 2}(F)\rvert\leq K_{2}$

1:Input: A size threshold $K_{2}$, a large constant $c_{2}$

2:Initialization: Sparse recovery sketch $\mathcal{L}$ in [11] with $k=K_{2}$
and $\delta=1/c_{2}$

3:First Pass:

4:for all $(e=(u,v),i)$ in the stream, $i\in\pm 1$ do

5: Update $\mathcal{L}$ with $(e,i)$

6:Decrement all coordinates in $\mathcal{L}$ by $1$

7:Denote the result of sparse recovery from $\mathcal{L}$ by $\mathcal{R}$

8:$p,m\leftarrow 0$

9:for $v\in\mathcal{R}$ do

10: $d_{v},l_{v}\leftarrow 0$ $\triangleright$ Degree and leaf counters

11:Second Pass:

12:for all $(e=(u,v),i)$ in the stream, $i\in\pm 1$ do

13: $m\leftarrow m+i$; $d_{u}\leftarrow d_{u}+i$; $d_{v}\leftarrow d_{v}+i$

14: if $u\notin\mathcal{R}$ and $v\notin\mathcal{R}$ then

15: $p\leftarrow p+i$

16: if $u\in\mathcal{R}$ and $v\notin\mathcal{R}$ then

17: $l_{u}\leftarrow l_{u}+i$

18: if $v\in\mathcal{R}$ and $u\notin\mathcal{R}$ then

19: $l_{v}\leftarrow l_{v}+i$

20:if $2m\neq n-\lvert\mathcal{R}\rvert+\sum_{v\in\mathcal{R}}d_{v}~{}$ then

21: Return FAIL

22:else

23: $\widehat{\lvert\mathit{Supp}(F)\rvert}\leftarrow\lvert\\{u\mid
u\in\mathcal{R}\text{ and }l(u)=1\\}\rvert+2p$

24: $\widehat{\lvert\mathit{Deg}_{\geq
2}(F)\rvert}\leftarrow\lvert\mathcal{R}\rvert$

25: Return $\widehat{\lvert\mathit{Supp}(F)\rvert}$ and
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$

######  Lemma 13.

Given threshold $K_{2}$, constant $c_{2}$, Subroutine 4 in two passes returns
both $\lvert\mathit{Supp}(F)\rvert$ and $\lvert\mathit{Deg}_{\geq 2}(F)\rvert$
in $\widetilde{\mathcal{O}}(K_{2})$ space. When $\lvert\mathit{Deg}_{\geq
2}(F)\rvert\leq K_{2}$, the failure probability is at most $1/c_{2}$.

###### Proof.

Note that in the first pass, only vertices in $\mathit{Deg}_{\geq 2}(F)$ are
sampled. This is because line 6 decreases the frequency of all vertices by
one, so leaves has 0 frequency and by the definition of $k$-sparse recovery,
they are not recovered by the sparse recovery data structure. Moreover, by
Theorem 3, when $\lvert\mathit{Deg}_{\geq 2}(F)\rvert\leq K_{2}$ (i.e., when
it is small), the sparse recovery fails with probability no more than
$1/c_{2}$.

Since the sparse recovery data structure might output a false positive result.
That is, a $k$-sparse vector when the original degree vector is not
$k$-sparse. We need to perform a sanity check at line 20 to ensure that the
returned result contains all $\mathit{Deg}_{\geq 2}(F)$ vertices, rather than
part of them. For this sanity check to work, we prove that the equality holds
if and only if $H=\mathit{Deg}_{\geq 2}(F)$.

To begin with, we prove that the equality holds if $H=\mathit{Deg}_{\geq
2}(F)$. This is trivial as for every graph $G$, we have the following
relationship between its edge count, $m$, and its total degree count:

$2m=\sum_{v\in V(G)}d(v)=n-\lvert\mathit{Deg}_{\geq
2}(G)\rvert+\sum_{v\in\mathit{Deg}_{\geq 2}(G)}d(v)\,.$

Next, we prove that the equality does not hold if $H\neq\mathit{Deg}_{\geq
2}(F)$. Suppose $H\neq\mathit{Deg}_{\geq 2}(F)$, note that by our argument
above, it is impossible to have $x$ such that $x\in H$ but
$x\notin\mathit{Deg}_{\geq 2}(F)$. Hence, we only consider the case where
$\exists x\in\mathit{Deg}_{\geq 2}(F)\text{ s.t. }x\notin H$. We have

$\displaystyle 2m-(n-\lvert H\rvert+\sum_{v\in H}d(v))$
$\displaystyle=n-\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\sum_{v\in\mathit{Deg}_{\geq 2}(F)}d(v)-(n-\lvert
H\rvert+\sum_{v\in H}d(v))$ $\displaystyle=\sum_{v\in\mathit{Deg}_{\geq
2}(F)}d(v)-\lvert\mathit{Deg}_{\geq 2}(F)\rvert-\sum_{v\in H}d(v)+\lvert
H\rvert$ $\displaystyle=\sum_{v\in\mathit{Deg}_{\geq 2}(F)\setminus
H}d(v)-\lvert\mathit{Deg}_{\geq 2}(F)\rvert-\sum_{v\in
H\setminus\mathit{Deg}_{\geq 2}(F)}d(v)+\lvert H\rvert$
$\displaystyle=\sum_{v\in\mathit{Deg}_{\geq 2}(F)\setminus
H}d(v)-\lvert\mathit{Deg}_{\geq 2}(F)\rvert-\lvert
H\setminus\mathit{Deg}_{\geq 2}(F)\rvert+\lvert H\rvert$
$\displaystyle=\sum_{v\in\mathit{Deg}_{\geq 2}(F)\setminus
H}d(v)-\lvert\mathit{Deg}_{\geq 2}(F)\setminus H\rvert$ $\displaystyle>0\,.$

The second-last equality holds because by our definition of
$\mathit{Deg}_{\geq 2}(F)$, all non-leaf vertices are in $\mathit{Deg}_{\geq
2}(F)$, hence vertices in $H\setminus\mathit{Deg}_{\geq 2}(F)$ are leaves and
have degree of 1. And the last inequality holds because vertices in
$\mathit{Deg}_{\geq 2}(F)$ have degree at least 2, and $\mathit{Deg}_{\geq
2}(F)\setminus H\neq\emptyset$. Hence, if some $\mathit{Deg}_{\geq 2}(F)$
vertices are not sampled, i.e., $\mathit{Deg}_{\geq 2}(F)\setminus
H\neq\emptyset$, then $2m\neq n-\lvert H\rvert+\sum_{v\in H}d(v)$.

It remains to prove that, conditional on all $\mathit{Deg}_{\geq 2}(F)$
vertices being sampled, both $\lvert\widehat{S}\rvert$ and
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ are correct estimates of
$\lvert\mathit{Supp}(F)\rvert$ and $\lvert\mathit{Deg}_{\geq 2}(F)\rvert$
respectively. If all $\mathit{Deg}_{\geq 2}(F)$ vertices are sampled
successfully, we can infer whether a vertex is a leaf or not by testing
whether it is in $H$ or not. As indicated by line 16 – 19, by counting the
number of leaves, $l_{v}$, for each $v\in H$, we can identify all the support
vertices in $H$. But not all support vertices have degree greater than 1, by
definition we can have support vertices of degree 1 in paths of length 2
($P_{2}$), such that each $P_{2}$ has two support vertices. Thus, we need to
also count the number of $P_{2}$, $p$. This is trivial as if an edge arrives
with none of its endpoints in $\mathit{Deg}_{\geq 2}(F)$, this edge must be an
instance of $P_{2}$.

Lastly, the space used by Algorithm 4 is $\widetilde{\mathcal{O}}(K_{3})$. In
the first pass, the sparse recovery structure takes
$\widetilde{\mathcal{O}}(K_{3})$ space to store. And in the second pass, for
each vertex in $\mathit{Supp}(F)$, we introduce two counters that can be both
stored in $\mathcal{O}(\log n)$ bits. Therefore the total space usage of
Algorithm 4 is $\widetilde{\mathcal{O}}(K_{3})$. ∎

##### Finalizing the Algorithms:

We run Lemma 11’s algorithm, Subroutine 3, and Subroutine 4 concurrently, with
$K_{1}=K_{2}=\mathcal{O}(\sqrt{n})$, $c_{1}=\mathcal{O}(\ln\delta^{-1})$, and
$c_{2}=\mathcal{O}(\delta^{-1})$. Returning the minimum of
$(3(n+\lvert\textit{Deg}_{1}(F)\rvert))/{8}$ and
$(n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)/{2}$, we
$4/3\cdot(1\pm{\varepsilon})$-approximate $\beta$ with probability
$(1-\delta)$ in $\widetilde{\mathcal{O}}(\sqrt{n})$ space.

Algorithm 5 Estimating $\beta(F)$ in forest $F$

1:Input: error rate ${\varepsilon}$, fail rate $\delta$

2:Initialization: $K_{1}\leftarrow\sqrt{n}$, $K_{2}\leftarrow 8\sqrt{n}$,
$c_{1}\leftarrow 3\ln(6\delta^{-1})$, $c_{2}\leftarrow\delta^{-1}$,
${\varepsilon}_{1}\leftarrow{\varepsilon}/2$

3:Run the following three subroutines concurrently:

4:$\lvert\widehat{\textit{Deg}_{1}}\rvert\leftarrow\text{
Lemma~{}\ref{lemma:Deg1} algorithm with~{}${\varepsilon}/2$ and~{}$\delta/2$}$

5:$\widehat{\lvert\mathit{Supp}(F)\rvert}\leftarrow\text{
Subroutine~{}\ref{alg:SLarge} with~{}$K_{1}$,~{}$c_{1}$,
and~{}${\varepsilon}_{1}$}$

6:$(\widehat{\lvert\mathit{Supp}(F)\rvert}^{\prime},\widehat{\lvert\mathit{Deg}_{\geq
2}\rvert}^{\prime})\leftarrow\text{ Subroutine~{}\ref{alg:dom-H2-Small}
with~{}$K_{2}$ and~{}$c_{2}$}$

7:if Subroutine 4 returns FAIL then

8: Return
$\widehat{\beta}\leftarrow\min\\{\frac{3(n+\lvert\widehat{\textit{Deg}_{1}}\rvert)}{8},\frac{n+\lvert\widehat{\textit{Deg}_{1}}\rvert-\lvert\widehat{\mathit{Supp}(F)}\rvert}{2}\\}$

9:else

10: $\lvert\widehat{\textit{Deg}_{1}}\rvert^{\prime}\leftarrow
n-\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert^{\prime}$

11: Return
$\widehat{\beta}\leftarrow\min\\{\frac{3(n+\lvert\widehat{\textit{Deg}_{1}}\rvert^{\prime})}{8},\frac{n+\lvert\widehat{\textit{Deg}_{1}}\rvert^{\prime}-\lvert\widehat{\mathit{Supp}(F)}\rvert^{\prime}}{2}\\}$

######  Theorem 17.

For every ${\varepsilon},\delta\in(0,1)$, Algorithm 5 estimates the
independence number $\beta(F)$ in a turnstile forest stream within factor
$4/3\cdot(1\pm{\varepsilon})$ with probability $(1-\delta)$ in
$\widetilde{\mathcal{O}}(\sqrt{n})$ space and two passes.

###### Proof.

By Theorem 11 and Corollary 1, the min between
$\frac{3(n+\lvert\textit{Deg}_{1}(F)\rvert)}{8}$ and
$\frac{n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert}{2}$ is
guaranteed to be a $4/3$ approximation of the independence number $\beta(F)$.
Hence, it suffices to show that we could either approximate both terms well,
or approximate the smaller term well.

When $\lvert\mathit{Deg}_{\geq 2}(F)\rvert\leq K_{2}=8\sqrt{n}$, the algorithm
returns at line 11. By Lemma 13, Subroutine 4 gives exact values of
$\lvert\mathit{Deg}_{\geq 2}(F)\rvert$ and $\lvert\mathit{Supp}(F)\rvert$ with
probability $1-1/c_{2}=1-\delta$. Also, since $n=\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\textit{Deg}_{1}(F)\rvert$ and $n$ is known, we can obtain
an exact value of $\lvert\textit{Deg}_{1}(F)\rvert$. Hence, no matter which
estimate is returned, it is a $4/3$ approximation of $\beta(F)$.

When $\lvert\mathit{Deg}_{\geq 2}(F)\rvert>8\sqrt{n}$, there are two cases to
consider. If $\lvert\mathit{Supp}(F)\rvert\geq\sqrt{n}$, we may return the
estimate of $\frac{3(n+\lvert\textit{Deg}_{1}(F)\rvert)}{8}$ or the estimate
of $\frac{n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert}{2}$
(line 8). On the one hand, if the estimate of
$\frac{3(n+\lvert\textit{Deg}_{1}(F)\rvert)}{8}$ is returned, by Lemma 11 we
know that the algorithm on line 4 outputs a $(1\pm\frac{{\varepsilon}}{2})$
estimate of $\lvert\textit{Deg}_{1}(F)\rvert$ with probability $1-\delta/2$.
Thus our result is a $4/3(1\pm{\varepsilon}/2)$ approximation of $\beta$.

On the other hand, if the estimate of
$\frac{n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert}{2}$ is
returned, by Lemma 12, Subroutine 3 gives a ($1\pm\frac{{\varepsilon}}{2}$)
estimate of $\lvert\mathit{Supp}(F)\rvert$ with probability

$1-3e^{-c_{1}/3}=1-3e^{-\ln(6\delta^{-1})}=1-\frac{\delta}{2},..$

Applying a union bound over successfully returning an estimate of
$\lvert\mathit{Supp}(F)\rvert$ and an estimate of
$\lvert\textit{Deg}_{1}(F)\rvert$, the probability of failure is at most
$\delta$. And on the upper-bound side, the approximation ratio is at most

$\displaystyle\frac{1}{2}\,(n+(1\pm\frac{{\varepsilon}}{2})\lvert\textit{Deg}_{1}(F)\rvert-(1\pm\frac{{\varepsilon}}{2})\lvert\mathit{Supp}(F)\rvert)$
$\displaystyle\leq\frac{1}{2}\,(n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert+\frac{{\varepsilon}}{2}\,(\lvert\textit{Deg}_{1}\rvert+\lvert
S\rvert))$
$\displaystyle\leq(1+{\varepsilon})\,\frac{1}{2}\,(n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)\,.$

The last inequality holds because
$\lvert\mathit{Supp}(F)\rvert\leq\lvert\textit{Deg}_{1}(F)\rvert\leq n$, thus
$\lvert\textit{Deg}_{1}(F)\rvert+\lvert\mathit{Supp}(F)\rvert$ is no more than
$2(n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)$.
Similarly, we prove the approximation ratio on the lower bound as

$\displaystyle\frac{1}{2}\,(n+(1\pm\frac{{\varepsilon}}{2})\lvert\textit{Deg}_{1}(F)\rvert-(1\pm\frac{{\varepsilon}}{2})\lvert\mathit{Supp}(F)\rvert)$
$\displaystyle\geq(1-{\varepsilon})\,\frac{1}{2}\,(n+\lvert\textit{Deg}_{1}(F)\rvert-\lvert\mathit{Supp}(F)\rvert)\,.$

Hence our algorithm returns a $4/3\cdot(1\pm{\varepsilon})$ approximation of
$\beta(F)$.

Lastly, if $\lvert\mathit{Supp}(F)\rvert<\sqrt{n}$, then by Lemma 12,
$\lvert\widehat{S}\rvert\leq 2\sqrt{n}$ with probability
$1-2e^{-\frac{c_{1}}{3{\varepsilon}^{2}}}$. By Theorem 9, we know that

$\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\geq(1-{\varepsilon})\cdot\lvert\mathit{Deg}_{\geq
2}(F)\rvert>\frac{\lvert\mathit{Deg}_{\geq 2}(F)\rvert}{2}$

holds with probability $1-\delta/2$ (if ${\varepsilon}<1/2$). Since
$\lvert\mathit{Deg}_{\geq 2}(F)\rvert\geq 8\sqrt{n}$, by applying a union
bound, we can claim that the probability of
$2\lvert\widehat{S}\rvert>\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ is at
most $2e^{-\frac{c_{1}}{3{\varepsilon}^{2}}}+\delta/2\leq\delta$. Therefore,
with probability $1-\delta$, the minimum between the two estimates is
$\frac{3(n+\lvert\widehat{\textit{Deg}_{1}(F)}\rvert)}{8}$. As shown before,
$\lvert\widehat{\textit{Deg}_{1}(F)}\rvert$ is a $1\pm{\varepsilon}$ estimate
of $\lvert\textit{Deg}_{1}(F)\rvert$, hence the return estimate is a
$4/3\cdot(1\pm{\varepsilon})$ approximation of $\beta(F)$ with probability
$1-\delta$.

The space usage of Algorithm 5 is the maximum space usage of its three sub-
algorithms, which is $\widetilde{\mathcal{O}}(\sqrt{n})$. ∎

####  4.2.2 One-pass and Two-pass Streaming Algorithms for Estimating the
Domination number $\gamma$

Lemma 9 and Theorem 12 allow us to $(3\pm{\varepsilon})$-approximate $\gamma$
in streaming forests using only polylog space.

######  Theorem 18.

For every ${\varepsilon},\delta\in(0,1)$ and forest $F$, the domination number
$\gamma$ can be $(3\pm{\varepsilon})$-approximated in turnstile streams with
probability $(1-\delta)$ and in
$\mathcal{O}(\log^{\mathcal{O}(1)}n\cdot\log\delta^{-1})$ space.

In addition, reusing the above algorithms for non-leaf vertices and support
vertices (Subroutine 3 and 4), and following a main algorithm similar to the
main algorithm (Algorithm 5) for independence number ($\beta$), we are able to
$2$-approximate domination number ($\gamma$) and $3/2$-approximate matching
number ($\phi$) in forest streams with $\widetilde{\mathcal{O}}(\sqrt{n})$
space and two passes. Our main algorithm (Algorithm 6) and theorem (Theorem
19) for approximating the domination number are shown below.

Algorithm 6 Main Algorithm for Estimating $\gamma$

1:Input: error rate ${\varepsilon}$ and fail rate $\delta$

2:Initialization: Set $K_{1}=\sqrt{n}$, $K_{2}=12\sqrt{n}$,
$c_{1}=3\ln(6\delta^{-1})$, $c_{2}=\delta^{-1}$,
${\varepsilon}_{1}={\varepsilon}$

3:Run the following algorithms concurrently:

4:1\. Algorithm for estimating $\lvert\mathit{Deg}_{\geq 2}\rvert$ with
${\varepsilon}$ and $\delta/2$, denote the returned result as
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$

5:2\. Subroutine 3 with $K_{1}$, $c_{1}$, and ${\varepsilon}_{1}$, denote the
returned result as $\lvert\widehat{S}\rvert$

6:3\. Subroutine 4 with $K_{2}$ and $c_{2}$, denote the returned result as
$\lvert\widehat{S}\rvert^{\prime}$ and $\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}$

7:if Subroutine 4 returns FAIL then

8: Return $\widehat{\gamma}=\max\\{\frac{2\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert}{3},\frac{\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert+\lvert\widehat{S}\rvert}{2}\\}$

9:else

10: Return $\widehat{\gamma}=\max\\{\frac{2\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}}{3},\frac{\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}+\lvert\widehat{S}\rvert^{\prime}}{2}\\}$

######  Theorem 19.

For every ${\varepsilon},\delta\in(0,1)$ and forest $F$ (with no isolated
vertices), Algorithm 6 estimates the domination number $\gamma(F)$ in a
turnstile stream within factor $2\cdot(1\pm{\varepsilon})$ with probability
$(1-\delta)$ in $\widetilde{\mathcal{O}}(\sqrt{n})$ space and two passes.

###### Proof.

By Theorem 13 and Corollary 2, the max between
$\frac{2\lvert\mathit{Deg}_{\geq 2}(F)\rvert}{3}$ and
$\frac{\lvert\mathit{Deg}_{\geq 2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}$
is guaranteed to be a $2$ approximation of the domination number $\gamma(F)$.
Thus it suffices to show that we could approximate both terms well, or we
could approximate the larger term well.

When $\lvert\mathit{Deg}_{\geq 2}(F)\rvert\leq K_{2}=12\sqrt{n}$, by Lemma 13,
Subroutine 4 succeeds with probability $1-1/c_{2}=1-\delta$. Thus, by the
design of the algorithm, we return our estimate at line 10. By Lemma 13,
conditional on successful returning, Subroutine 4 gives exact values of
$\lvert\mathit{Deg}_{\geq 2}(F)\rvert$ and $\lvert\mathit{Supp}(F)\rvert$.
Hence we have a $2$-approximation of $\gamma(F)$.

When $\lvert\mathit{Deg}_{\geq 2}(F)\rvert>12\sqrt{n}$, there are two cases to
consider. If $\lvert\mathit{Supp}(F)\rvert\geq\sqrt{n}$, then the algorithm
might return the estimate of $\frac{2\lvert\mathit{Deg}_{\geq 2}(F)\rvert}{3}$
or the estimate of $\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(F)\rvert}{2}$. On the one hand, if the
estimate of $\frac{2\lvert\mathit{Deg}_{\geq 2}(F)\rvert}{3}$ is returned, by
Theorem 9, we know that the algorithm on line 4 outputs a
$(1\pm{\varepsilon})$ estimate of $\lvert\mathit{Deg}_{\geq 2}(F)\rvert$ with
probability $1-\delta/2$. Hence we obtain a $2(1\pm{\varepsilon})$
approximation of $\gamma$.

On the other hand, if the estimate of $\frac{\lvert\mathit{Deg}_{\geq
2}(F)\rvert+\lvert\mathit{Supp}(S)\rvert}{2}$ is returned by our algorithm, we
know that by Lemma 12, Subroutine 3 gives a ($1\pm{\varepsilon}$) estimate of
$\lvert\mathit{Supp}(S)\rvert$ with probability

$1-3e^{-c_{1}/3}=1-3e^{-\ln(6\delta^{-1})}=1-\frac{\delta}{2}\,.$

Applying a union bound over successfully returning an estimate of
$\lvert\mathit{Supp}(F)\rvert$ and an estimate of $\lvert\mathit{Deg}_{\geq
2}(F)\rvert$, the probability of failure is at most $\delta$. And the error
rate is still $1\pm{\varepsilon}$ as we are summing up the two terms. Hence,
the returned estimate is still a $2(1\pm{\varepsilon})$ approximation of
$\gamma$.

Lastly, if $\lvert\mathit{Supp}(F)\rvert<\sqrt{n}$, then by Lemma 12,
$\lvert\widehat{S}\rvert\leq 2\sqrt{n}$ with probability
$1-2e^{-\frac{c_{1}}{3}}$. By Theorem 9, if ${\varepsilon}<1/2$, then

$\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\geq(1-{\varepsilon})\lvert\mathit{Deg}_{\geq
2}(F)\rvert>\frac{\lvert\mathit{Deg}_{\geq 2}(F)\rvert}{2}$

with probability $1-\delta/2$. Since we have $\lvert\mathit{Deg}_{\geq
2}(F)\rvert>12\sqrt{n}$, we can bound the probability of
$3\lvert\widehat{S}\rvert\leq\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ as

$\displaystyle\Pr\big{[}3\lvert\widehat{S}\rvert\leq\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\big{]}$ $\displaystyle=\Pr\big{[}\lvert\widehat{S}\rvert\leq
2\sqrt{n}\wedge\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert>6\sqrt{n}\big{]}$
$\displaystyle\geq
1-\Pr\big{[}\lvert\widehat{S}\rvert>2\sqrt{n}\big{]}-\Pr\big{[}\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\leq 6\sqrt{n}\big{]}$ $\displaystyle\geq
1-2e^{-\frac{c_{1}}{3}}-\delta/2$ $\displaystyle\geq 1-\delta\,,$

where we apply the union bound in the first inequality. Therefore, with
probability at least $1-\delta$, the maximum between the two estimates,
$\frac{2\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert}{3}$ and
$\frac{\lvert\mathit{Deg}_{\geq 2}\rvert+\lvert S\rvert}{2}$, is
$\frac{2\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert}{3}$. As shown before,
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ is a $1\pm{\varepsilon}$
estimate of $\lvert\mathit{Deg}_{\geq 2}(F)\rvert$, hence the returned
estimate is a $2\cdot(1\pm{\varepsilon})$ approximation of $\gamma(F)$ with
probability $1-\delta$.

The space usage of Algorithm 6 is the maximum space usage of its three sub-
algorithms, which is $\widetilde{\mathcal{O}}(\sqrt{n})$. ∎

####  4.2.3 One-pass and Two-pass Streaming Algorithms for Estimating the
Matching number $\phi$

Similarly, combining Lemma 9 and Theorem 14, we are able to
$(2\pm{\varepsilon})$-approximate $\phi$ in streaming forests using only
polylog space.

######  Theorem 20.

For every ${\varepsilon},\delta\in(0,1)$ and forest $F$, the matching number
$\phi$ can be $(2\pm{\varepsilon})$-approximated in turnstile streams with
probability $(1-\delta)$ and in
$\mathcal{O}(\log^{\mathcal{O}(1)}n\cdot\log\delta^{-1})$ space.

The approximation ratio can be further improved to $3/2$ when we allow an
additional passes and using a total of $\widetilde{\mathcal{O}}(\sqrt{n})$
space. Our main algorithm (Algorithm 7) and theorem (Theorem 21) for
approximating the matching number are shown below.

Algorithm 7 Main Algorithm for Estimating $\phi$

1:Input: error rate ${\varepsilon}$ and fail rate $\delta$

2:Initialization: Set $K_{1}=\sqrt{n}$, $K_{2}=8\sqrt{n}$,
$c_{1}=3\ln(6\delta^{-1})$, $c_{2}=\delta^{-1}$,
${\varepsilon}_{1}={\varepsilon}$

3:Run the following algorithms concurrently:

4:1\. Algorithm for estimating $\lvert\mathit{Deg}_{\geq 2}\rvert$ with
${\varepsilon}$ and $\delta/2$, denote the returned result as
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$

5:2\. Degree-counting algorithms to determine the number of tree components,
$C$.

6:3\. Subroutine 3 with $K_{1}$, $c_{1}$, and ${\varepsilon}_{1}$, denote the
returned result as $\lvert\widehat{S}\rvert$

7:4\. Subroutine 4 with $K_{2}$ and $c_{2}$, denote the returned result as
$\lvert\widehat{S}\rvert^{\prime}$ and $\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}$

8:if Subroutine 4 returns FAIL then

9: Return $\widehat{\phi}=\max\\{\frac{3(\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert+C)}{4},\frac{\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert+\lvert\widehat{S}\rvert}{2}\\}$

10:else

11: Return $\widehat{\phi}=\max\\{\frac{3(\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}+C)}{4},\frac{\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert^{\prime}+\lvert\widehat{S}\rvert^{\prime}}{2}\\}$

######  Theorem 21.

For every ${\varepsilon},\delta\in(0,1)$ and forest $F$ (with no isolated
vertices), Algorithm 5 estimates the matching number $\phi(F)$ in a turnstile
stream within factor $3/2\cdot(1\pm{\varepsilon})$ with probability
$(1-\delta)$ in $\widetilde{\mathcal{O}}(\sqrt{n})$ space and two passes.

###### Proof.

By Theorem 15 and Corollary 3, the max between
$\frac{3(\lvert\mathit{Deg}_{\geq 2}\rvert+C)}{4}$ and
$\frac{\lvert\mathit{Deg}_{\geq 2}\rvert+\lvert\mathit{Supp}\rvert}{2}$ is
guaranteed to be a $3/2$ approximation of the matching number $\phi$. Thus it
suffices to show that we could approximate both terms well, or we could
approximate the larger term well.

When $\lvert\mathit{Deg}_{\geq 2}\rvert\leq K_{2}=8\sqrt{n}$, by Lemma 13,
Subroutine 4 succeeds with probability $1-1/c_{2}=1-\delta$. Thus, by the
design of the algorithm, we return our estimate at line 11. By Lemma 13,
conditional on successful returning, Subroutine 4 gives exact values of
$\lvert\mathit{Deg}_{\geq 2}\rvert$ and $\lvert\mathit{Supp}\rvert$. Hence we
have a $3/2$-approximation of $\phi$.

When $\lvert\mathit{Deg}_{\geq 2}\rvert>8\sqrt{n}$, there are two cases to
consider. If $\lvert\mathit{Supp}\rvert\geq\sqrt{n}$, then the algorithm might
return the estimate of $\frac{3(\lvert\mathit{Deg}_{\geq 2}\rvert+C)}{4}$ or
the estimate of $\frac{\lvert\mathit{Deg}_{\geq
2}\rvert+\lvert\mathit{Supp}\rvert}{2}$. Note $C$ is an exact estimate of the
number of tree components. On the one hand, if the estimate of
$\frac{3(\lvert\mathit{Deg}_{\geq 2}\rvert+C)}{3}$ is returned, by Theorem 9,
we know that the algorithm on line 4 outputs a $(1\pm{\varepsilon})$ estimate
of $\lvert\mathit{Deg}_{\geq 2}\rvert$ with probability $1-\delta/2$. Hence we
obtain a $3/2(1\pm{\varepsilon})$ approximation of $\phi$. On the other hand,
if the estimate of $\frac{\lvert\mathit{Deg}_{\geq
2}\rvert+\lvert\mathit{Supp}\rvert}{2}$ is returned by our algorithm, we know
that by Lemma 12, Subroutine 3 gives a ($1\pm{\varepsilon}$) estimate of
$\lvert\mathit{Supp}\rvert$ with probability

$1-3e^{-c_{1}/3}=1-3e^{-\ln(6\delta^{-1})}=1-\frac{\delta}{2}\,.$

Apply a union bound over successfully returning an estimate of
$\lvert\mathit{Supp}\rvert$ and an estimate of $\lvert\mathit{Deg}_{\geq
2}\rvert$, the probability of failure is at most $\delta$. And the error rate
is still $1\pm{\varepsilon}$ as we are summing up the two terms. Hence, the
returned estimate is still a $3/2(1\pm{\varepsilon})$ approximation of $\phi$.

Lastly, if $\lvert\mathit{Supp}\rvert<\sqrt{n}$, then by Lemma 12,
$\lvert\widehat{S}\rvert\leq 2\sqrt{n}$ with probability
$1-2e^{-\frac{c_{1}}{3}}$. By Theorem 9, if ${\varepsilon}<1/2$, then

$\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\geq(1-{\varepsilon})\lvert\mathit{Deg}_{\geq
2}\rvert>\frac{\lvert\mathit{Deg}_{\geq 2}\rvert}{2}$

with probability $1-\delta/2$. Since we have $\lvert\mathit{Deg}_{\geq
2}\rvert>8\sqrt{n}$, we can bound the probability of
$2\lvert\widehat{S}\rvert\leq\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ as

$\displaystyle\Pr\big{[}2\lvert\widehat{S}\rvert\leq\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\big{]}$ $\displaystyle=\Pr\big{[}\lvert\widehat{S}\rvert\leq
2\sqrt{n}\wedge\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert>4\sqrt{n}\big{]}$
$\displaystyle\geq
1-\Pr\big{[}\lvert\widehat{S}\rvert>2\sqrt{n}\big{]}-\Pr\big{[}\lvert\widehat{\mathit{Deg}_{\geq
2}}\rvert\leq 4\sqrt{n}\big{]}$ $\displaystyle\geq
1-2e^{-\frac{c_{1}}{3}}-\delta/2$ $\displaystyle\geq 1-\delta\,,$

where we apply the union bound in the first inequality. Therefore, with
probability at least $1-\delta$, the maximum between the two estimates,
$\frac{3(\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert+C)}{4}$ and
$\frac{\lvert\mathit{Deg}_{\geq 2}\rvert+\lvert S\rvert}{2}$, is
$\frac{3(\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert+C)}{4}$. As shown before,
$\lvert\widehat{\mathit{Deg}_{\geq 2}}\rvert$ is a $1\pm{\varepsilon}$
estimate of $\lvert\mathit{Deg}_{\geq 2}\rvert$, hence the returned estimate
is a $3/2\cdot(1\pm{\varepsilon})$ approximation of $\phi$ with probability
$1-\delta$.

The space usage of Algorithm 21 is the maximum space usage of its four sub-
algorithms, which is $\widetilde{\mathcal{O}}(\sqrt{n})$. ∎

##  5 Conclusion & Open Questions

We designed Carawayto estimate the Caro-Wei bound. It improves on Halldórsson