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 logn) 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²) space, where d' is the average degree of G. We further prove that space Ω(d' / c²) 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³ 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.