TY - JOUR

T1 - On coalescence time in graphs–When is coalescing as fast as meeting?

AU - Kanade, Varun

AU - Mallmann-Trenn, Frederik

AU - Sauerwald, Thomas

N1 - Funding Information:
F. Mallmann-Trenn was supported in part by EPSRC grant EP/W005573/1.
Publisher Copyright:
© 2023 Copyright held by the owner/author(s).

PY - 2023/4/21

Y1 - 2023/4/21

N2 - 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 log2 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(n3). 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.

AB - 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 log2 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(n3). 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.

UR - http://www.scopus.com/inward/record.url?scp=85159235302&partnerID=8YFLogxK

U2 - 10.1145/3576900

DO - 10.1145/3576900

M3 - Article

SN - 1549-6325

VL - 19

JO - Acm Transactions On Algorithms

JF - Acm Transactions On Algorithms

IS - 2

M1 - 18

ER -