In this note, we present a simple algorithm for computing a \emph{$k$-connectivity certificate} in dynamic graph streams. Our algorithm uses $O(n \log^2 n \cdot \max\{k, \log n \log k\})$ bits of space which improves upon the $O(kn \log^3 n)$-space algorithm of Ahn, Guha, and McGregor (SODA'12). For the values of $k$ that are truly sublinear, our space usage \emph{very nearly} matches the known lower bound $\Omega(n \log^2 n \cdot \max\{k, \log n\})$ established by Nelson and Yu (SODA'19; implicit) and Robinson (DISC'24). In particular, our algorithm fully settles the space complexity at $\Theta(kn \log^2{n})$ for $k = \Omega(\log n \log \log n)$, and bridges the gap down to only a doubly-logarithmic factor of $O(\log \log n)$ for a smaller range of $k = o(\log n \log \log n)$.
翻译：本文提出一种在动态图流中计算\emph{$k$连通性证书}的简洁算法。该算法使用$O(n \log^2 n \cdot \max\{k, \log n \log k\})$比特的存储空间，改进了Ahn、Guha与McGregor（SODA'12）提出的$O(kn \log^3 n)$空间算法。对于真正亚线性的$k$值，我们的空间使用量\emph{极其接近}Nelson与Yu（SODA'19；隐式）以及Robinson（DISC'24）建立的已知下界$\Omega(n \log^2 n \cdot \max\{k, \log n\})$。特别地，当$k = \Omega(\log n \log \log n)$时，我们的算法完全确定了$\Theta(kn \log^2{n})$的空间复杂度；而对于更小的$k = o(\log n \log \log n)$范围，则将空间差距缩小至仅$O(\log \log n)$的双对数因子。
相关内容
微信扫码咨询专知VIP会员