On coalescence time in graphs–when is coalescing as fast as meeting?
<p>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 <em>coalesce...
| Glavni autori: | , , |
|---|---|
| Format: | Journal article |
| Jezik: | English |
| Izdano: |
Association for Computing Machinery
2023
|
| _version_ | 1826309987112058880 |
|---|---|
| author | Kanade, V Mallmann-Trenn, F Sauerwald, T |
| author_facet | Kanade, V Mallmann-Trenn, F Sauerwald, T |
| author_sort | Kanade, V |
| collection | OXFORD |
| description | <p>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 <em>coalescence time</em> is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper et al. [14] and Cooper et al. [19], the coalescence time for graphs such as binary trees, <em>d</em>-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved.</p>
<p>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 <sup>2</sup><em>n</em>), the coalescence time of <em>n</em> 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 <em>O</em>(<em>n</em><sup>3</sup>). By duality, our results yield identical bounds on the voter model.</p>
<p>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 [12], as well as those by Aldous and Fill [2].</p> |
| first_indexed | 2024-03-07T07:43:56Z |
| format | Journal article |
| id | oxford-uuid:6ec9e434-5136-4974-974b-8d6619a52882 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:43:56Z |
| publishDate | 2023 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:6ec9e434-5136-4974-974b-8d6619a528822023-05-19T08:20:16ZOn coalescence time in graphs–when is coalescing as fast as meeting?Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6ec9e434-5136-4974-974b-8d6619a52882EnglishSymplectic ElementsAssociation for Computing Machinery2023Kanade, VMallmann-Trenn, FSauerwald, T<p>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 <em>coalescence time</em> is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper et al. [14] and Cooper et al. [19], the coalescence time for graphs such as binary trees, <em>d</em>-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved.</p> <p>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 <sup>2</sup><em>n</em>), the coalescence time of <em>n</em> 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 <em>O</em>(<em>n</em><sup>3</sup>). By duality, our results yield identical bounds on the voter model.</p> <p>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 [12], as well as those by Aldous and Fill [2].</p> |
| spellingShingle | Kanade, V Mallmann-Trenn, F Sauerwald, T On coalescence time in graphs–when is coalescing as fast as meeting? |
| title | On coalescence time in graphs–when is coalescing as fast as meeting? |
| title_full | On coalescence time in graphs–when is coalescing as fast as meeting? |
| title_fullStr | On coalescence time in graphs–when is coalescing as fast as meeting? |
| title_full_unstemmed | On coalescence time in graphs–when is coalescing as fast as meeting? |
| title_short | On coalescence time in graphs–when is coalescing as fast as meeting? |
| title_sort | on coalescence time in graphs when is coalescing as fast as meeting |
| work_keys_str_mv | AT kanadev oncoalescencetimeingraphswheniscoalescingasfastasmeeting AT mallmanntrennf oncoalescencetimeingraphswheniscoalescingasfastasmeeting AT sauerwaldt oncoalescencetimeingraphswheniscoalescingasfastasmeeting |