Title: Independent Set Size Approximation in Graph Streams,
Abstract: We study the problem of estimating the size of independent sets in a graph
$G$ defined by a stream of edges. Our approach relies on the Caro-Wei bound,
which expresses the desired quantity in terms of a sum over nodes of the
reciprocal of their degrees, denoted by $\beta(G)$. Our results show that
$\beta(G)$ can be approximated accurately, based on a provided lower bound on
$\beta$. Stronger results are possible when the edges are promised to arrive
grouped by an incident node. In this setting, we obtain a value that is at most
a logarithmic factor below the true value of $\beta$ and no more than the true
independent set size. To justify the form of this bound, we also show an
$\Omega(n/\beta)$ lower bound on any algorithm that approximates $\beta$ up to
a constant factor.