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 $β(G)$. Our results show that $β(G)$ can be approximated accurately, based on a provided lower bound on $β$. 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 $β$ and no more than the true independent set size. To justify the form of this bound, we also show an $Ω(n/β)$ lower bound on any algorithm that approximates $β$ up to a constant factor.