## G. Cormode, J. Dark, and C. Konrad.
Approximating the caro-wei bound for independent sets in graph
streams.
In *International Symposium on Combinatorial Optimization*, 2018.

The Caro-Wei bound states that every graph *G*=(*V*, *E*) contains an independent set of size at
least β(*G*) := σ_{v inV} (1)/(*deg*_{G}(*v*) + 1), where *deg*_{G}(*v*) denotes the degree of vertex *v*.
Halldórsson et al. gave a randomized one-pass streaming algorithm that computes an independent
set of expected size β(*G*) using *O*(*n* log*n*) 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*(*d*' log(*n*) /*c*^{2}) space,
where *d*' is the average degree of *G*. We further prove
that space Ω(*d*' / *c*^{2}) 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 algorithm even for graphs with arbitrarily large average degree, we employ
an alternative notion of approximation: We give a one-pass streaming algorithm with space *O*(log^{3} *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.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*