Approximating the Caro-Wei Bound for Independent Sets in Graph Streams
Approximating the Caro-Wei Bound for Independent Sets in Graph Streams
复制标题
DOI：
10.1007/978-3-319-96151-4_9
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Graham Cormode;J. Dark;C. Konrad
中科院分区：
文献类型：
--
作者：
Graham Cormode;J. Dark;C. Konrad
Caro-Wei边界指出，每个图至少包含一个独立的大小集，其中表示顶点的程度。Halldórsson等人。[1]给出了一个随机的单次流算法，该算法计算了一组独立的预期大小。本文给出了流算法和近似Caro-Wei界本身的下界。在边缘到达模型中，我们提出了一种利用空间（其中为g的平均度）的一遍近似流算法。我们进一步证明了空间是必要的，使得我们的算法几乎是最优的。这个下界甚至在顶点到达模型中也成立，在顶点到达模型中，顶点一个接一个地到达，它们的关联边连接到先前到达的顶点。为了获得多对数空间算法，即使对于具有任意大的平均度的图，我们也采用了另一种近似概念：我们在顶点到达模型中给出一个带有空间的单遍流算法，该算法输出的值最多低于真实值的对数因子，并且不超过最大独立集大小。
The Caro-Wei bound states that every graphcontains an independent set of size at least, wheredenotes the degree of vertexv. Halldórsson et al. [1] gave a randomized one-pass streaming algorithm that computes an independent set of expected sizeusingspace. 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-passc-approximation streaming algorithm that usesspace, whereis the average degree ofG. We further prove that spaceis necessary, rendering our algorithm almost optimal. This lower bound holds even in thevertex 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 spacein the vertex arrival model that outputs a value that is at most a logarithmic factor below the true value ofand no more than the maximum independent set size.