On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
复制标题
DOI：
10.1145/3576900
复制
发表时间：
2023-04-01
影响因子：
1.3
通讯作者：
Sauerwald, Thomas
中科院分区：
文献类型：
--
作者：
Kanade, Varun;Mallmann-Trenn, Frederik;Sauerwald, Thomas
合并随机游动是一个基本的分布式过程，其中一组粒子在无向图上执行独立的离散时间随机游动。当两个或多个粒子在给定节点相遇时，它们合并并继续作为一个随机行走。聚结时间被定义为从每个节点处的一个粒子开始直到仅剩下一个粒子的预期时间。尽管最近取得了诸如库珀等人的进展，诸如二叉树、D维环面、超立方体以及更一般地顶点传递图之类的图的合并时间仍然没有解决。我们提供了一个强大的工具包，结果在严格的边界，包括上述的各种拓扑结构。相遇时间定义为两个随机游动同时到达同一节点所需的最坏情况下的预期时间。作为一般的结果，我们建立的图，其会议时间只是略大于混合时间（log（2）n的一个因素），合并时间的n个随机游动等于会议时间常数的因素。这个上限是补充建设的一个图形的家庭证明，这一结果是最好的可能常数的因素。最后，我们证明了一个严格的最坏情况下的结合时间为O（n（3））。通过对偶性，我们的结果在选民模型上产生相同的边界。我们的技术也产生了一个新的边界上的命中时间和覆盖时间的定期图，改进和收紧以前的结果布罗德和卡林，以及那些由Aldous和填充。
Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as that of Cooper et al., the coalescence time for graphs, such as binary trees, d-dimensional tori, hypercubes, and, more generally, vertex-transitive graphs, remains unresolved. We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log(2) n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst-case bound for the coalescence time of O(n(3)). By duality, our results yield identical bounds on the voter model. Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.