Approximating the Caro-Wei Bound for Independent Sets in Graph Streams

The Caro-Wei bound states that every graph G = (V,E) contains an independent set of size at least β(G) :=Pv∈V 1 degG(v)+1, where degG(v) denotesthedegreeofvertex v.Halld´orssonetal.[1]gavearandomizedone-pass streaming algorithm that computes an independent set of expected size β(G) using O(nlogn) space. In this paper, we give streaming algorithms and a lower bound for approximating the Caro-Wei bound itself. In the edge arrival model, we present a one-pass c-approximation streaming algorithm that uses O(dlog(n)/c2) space, where d is the average degree of G. We further prove that space Ω(d/c2) is necessary, rendering our algorithm almost optimal. This lower bound holds even in the vertex arrival model, where vertices arrive one by one together with their incident edges that connect to vertices that have previously arrived. In order to obtain a poly-logarithmic space algorithmevenforgraphswitharbitrarilylargeaveragedegree,weemployanalternative notion of approximation: We give a one-pass streaming algorithm with space O(log3 n) in the vertex arrival model that outputs a value that is at most a logarithmic factor below the true value of β and no more than the maximum independent set size.