Independent Set Size Approximation in Graph Streams
Independent Set Size Approximation in Graph Streams
复制标题
DOI：
--
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Graham Cormode;J. Dark;C. Konrad
中科院分区：
文献类型：
--
作者：
Graham Cormode;J. Dark;C. Konrad
我们研究了由边缘流定义的图$ g $中估计独立集的大小的问题。我们的方法依赖于caro-wei的界限，该界限以$ \ beta（g）$表示的互惠节点的总和表示所需的数量。我们的结果表明，$ \ beta（g）$可以根据$ \ beta $提供的下限来准确地近似。当承诺通过事件节点分组边缘时，可能会更强的结果。在这种情况下，我们获得的值最多是对数因子低于$ \ beta $的真实值，而不必超过真正的独立设置大小。为了证明这种界限的合理性，我们还显示了$ \ omega（n/\ beta）$下限的任何算法，该算法将$ \ beta $近似于恒定因素。
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 $\beta(G)$. Our results show that $\beta(G)$ can be approximated accurately, based on a provided lower bound on $\beta$. 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 $\beta$ and no more than the true independent set size. To justify the form of this bound, we also show an $\Omega(n/\beta)$ lower bound on any algorithm that approximates $\beta$ up to a constant factor.